Array modification (push, pop, shift, unshift) in Ruby - Time & Space Complexity

Time Complexity: Array modification (push, pop, shift, unshift)

O(1) for push/pop, O(n) for shift/unshift

Understanding Time Complexity

When we add or remove items from an array, the time it takes can change depending on how we do it.

We want to know how the work grows when we use push, pop, shift, or unshift on arrays.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

arr = []
arr.push(10)      # Add item at the end
arr.pop           # Remove item from the end
arr.unshift(5)    # Add item at the start
arr.shift         # Remove item from the start
    

This code shows adding and removing items at both ends of an array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding or removing one item at either end of the array.
• How many times: Each operation happens once, but internally some may move many items.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations for push/pop	Approx. Operations for shift/unshift
10	1 (simple add/remove)	10 (move all items)
100	1 (simple add/remove)	100 (move all items)
1000	1 (simple add/remove)	1000 (move all items)

Pattern observation: push and pop take about the same small time no matter the size, but shift and unshift take longer as the array grows.

Final Time Complexity

Time Complexity: O(1) for push/pop, O(n) for shift/unshift

This means adding or removing at the end is fast and steady, but doing it at the start gets slower as the array gets bigger.

Common Mistake

[X] Wrong: "All array add/remove operations take the same time."

[OK] Correct: Adding or removing at the start needs to move all other items, so it takes longer when the array is big.

Interview Connect

Understanding these differences helps you explain why some array operations are faster, showing you know how data structures work behind the scenes.

Self-Check

"What if we used a linked list instead of an array? How would the time complexity for adding or removing at the start change?"

Practice

1. Which Ruby array method adds an element to the end of the array?

easy

A. shift

B. pop

C. push

D. unshift

Solution

1. Step 1: Understand the purpose of push

   The push method adds an element to the end of an array.

2. Step 2: Compare with other methods

   pop removes the last element, shift removes the first, and unshift adds to the front.

3. Final Answer:

   push -> Option C

4. Quick Check:

   push adds to end [OK]

Hint: Remember: push = add end, unshift = add front [OK]

Common Mistakes:

• Confusing push with pop
• Mixing shift and unshift
• Thinking pop adds elements

2. Which of the following is the correct syntax to remove the first element from an array arr in Ruby?

easy

A. arr.shift()

B. arr.pop()

C. arr.unshift()

D. arr.push()

Solution

1. Step 1: Identify method to remove first element

   The shift method removes and returns the first element of an array.

2. Step 2: Check syntax correctness

   Calling arr.shift() correctly removes the first element.

3. Final Answer:

   arr.shift() -> Option A

4. Quick Check:

   shift removes first element [OK]

Hint: shift removes first, pop removes last [OK]

Common Mistakes:

• Using pop to remove first element
• Calling unshift to remove elements
• Forgetting parentheses

3. What will be the output of the following Ruby code?

arr = [1, 2, 3]
arr.push(4)
arr.shift
p arr

medium

A. [1, 2, 3]

B. [1, 2, 3, 4]

C. [4, 1, 2, 3]

D. [2, 3, 4]

Solution

1. Step 1: Execute push(4) on array

   Adding 4 to the end changes array from [1, 2, 3] to [1, 2, 3, 4].

2. Step 2: Execute shift to remove first element

   Removing first element (1) results in [2, 3, 4].

3. Final Answer:

   [2, 3, 4] -> Option D

4. Quick Check:

   push adds end, shift removes front = [2, 3, 4] [OK]

Hint: push adds end, shift removes front, watch order [OK]

Common Mistakes:

• Ignoring shift effect
• Thinking push adds front
• Confusing pop with shift

4. The following Ruby code is intended to add 0 to the front of the array nums and then remove the last element. What is the error?

nums = [1, 2, 3]
nums.unshift(0)
nums.pop()

medium

A. No error; code works correctly

B. pop() should be called before unshift()

C. unshift() does not add elements to array

D. pop() removes the first element, not the last

Solution

1. Step 1: Understand unshift(0) effect

   This adds 0 to the front, changing [1, 2, 3] to [0, 1, 2, 3].

2. Step 2: Understand pop() effect

   This removes the last element (3), resulting in [0, 1, 2].

3. Final Answer:

   No error; code works correctly -> Option A

4. Quick Check:

   unshift adds front, pop removes last = correct [OK]

Hint: unshift adds front, pop removes last, order matters [OK]

Common Mistakes:

• Thinking pop removes first element
• Believing unshift does not add
• Swapping order of operations unnecessarily

5. Given the array data = [10, 20, 30], which sequence of method calls will result in [5, 10, 20]?

hard

A. data.push(5).shift()

B. data.unshift(5).pop()

C. data.shift().unshift(5)

D. data.pop().unshift(5)

Solution

1. Step 1: Apply unshift(5) to add 5 at front

   Array changes from [10, 20, 30] to [5, 10, 20, 30].

2. Step 2: Apply pop() to remove last element

   Removing last element (30) results in [5, 10, 20].

3. Final Answer:

   data.unshift(5).pop() -> Option B

4. Quick Check:

   unshift adds front, pop removes last = [5, 10, 20] [OK]

Hint: Add front with unshift, then remove last with pop [OK]

Common Mistakes:

• Using push instead of unshift
• Removing first element instead of last
• Chaining methods incorrectly