Dynamic Stack Using Resizable Array in DSA Go - Time & Space Complexity

Time Complexity: Dynamic Stack Using Resizable Array

O(1) amortized

Understanding Time Complexity

We want to understand how the time to add or remove items from a dynamic stack changes as the stack grows.

How does resizing the array affect the speed of stack operations?

Scenario Under Consideration

Analyze the time complexity of the following dynamic stack push operation.

func (s *Stack) Push(value int) {
    if s.size == len(s.array) {
        newArray := make([]int, 2*len(s.array))
        copy(newArray, s.array)
        s.array = newArray
    }
    s.array[s.size] = value
    s.size++
}
    

This code adds a value to the stack, doubling the array size when full.

Identify Repeating Operations

Look at what repeats when pushing many items.

• Primary operation: Adding one item to the array (simple assignment).
• How many times: Once per push, except when resizing.
• Resizing operation: Copying all current items to a new larger array.
• How many times resizing happens: Only when the array is full, which happens less often as size grows.

How Execution Grows With Input

Adding items usually takes a quick step, but sometimes it takes longer to copy all items when resizing.

Input Size (n)	Approx. Operations
10	About 10 simple adds + 1 or 2 resizes copying up to 10 items
100	About 100 simple adds + 2-3 resizes copying up to 100 items
1000	About 1000 simple adds + 4-5 resizes copying up to 1000 items

Pattern observation: Most pushes are fast; resizing happens rarely but costs more, so average cost stays low.

Final Time Complexity

Time Complexity: O(1) amortized

This means each push usually takes constant time, but occasionally takes longer when resizing, averaging out to constant time per push.

Common Mistake

[X] Wrong: "Every push takes a long time because of copying during resizing."

[OK] Correct: Resizing happens rarely and copying cost spreads over many pushes, so most pushes are quick.

Interview Connect

Understanding amortized time helps you explain why dynamic arrays and stacks are efficient in real programs, showing you know how data structures work under the hood.

Self-Check

"What if we increased the array size by only 1 each time instead of doubling? How would the time complexity change?"

Practice

1. What is the main advantage of using a dynamic stack implemented with a resizable array compared to a fixed-size array stack?

easy

A. It can grow or shrink automatically as elements are pushed or popped.

B. It uses less memory than a linked list stack.

C. It always has a fixed maximum size.

D. It does not require resizing when full.

Solution

1. Step 1: Understand fixed-size array stack limitation

   A fixed-size array stack cannot grow beyond its initial capacity, causing overflow if too many elements are pushed.

2. Step 2: Understand dynamic stack behavior

   A dynamic stack with a resizable array automatically increases or decreases its size when needed, avoiding overflow and wasting less memory.

3. Final Answer:

   It can grow or shrink automatically as elements are pushed or popped. -> Option A

4. Quick Check:

   Dynamic resizing = Automatic growth/shrink [OK]

Hint: Dynamic arrays resize automatically on overflow or underflow [OK]

Common Mistakes:

• Thinking dynamic stack has fixed size
• Confusing linked list stack with array stack
• Assuming no resizing is needed

2. Which of the following Go code snippets correctly doubles the size of the stack's underlying array when it is full?

easy

A. stack.data = append(stack.data, make([]int, len(stack.data))...)

B. newData := make([]int, len(stack.data)*2); copy(newData, stack.data); stack.data = newData

C. stack.data = stack.data[:len(stack.data)*2]

D. stack.data = make([]int, len(stack.data)/2)

Solution

1. Step 1: Understand how to resize an array in Go

   Go slices cannot be resized directly; we create a new slice with double capacity and copy old elements.

2. Step 2: Check each option

   newData := make([]int, len(stack.data)*2); copy(newData, stack.data); stack.data = newData creates a new slice double the size, copies old data, and assigns it back, which is correct resizing.

3. Final Answer:

   newData := make([]int, len(stack.data)*2); copy(newData, stack.data); stack.data = newData -> Option B

4. Quick Check:

   Resize by new slice + copy = newData := make([]int, len(stack.data)*2); copy(newData, stack.data); stack.data = newData [OK]

Hint: Resize by new slice + copy old data [OK]

Common Mistakes:

• Using append to resize underlying array incorrectly
• Slicing beyond capacity without copying
• Reducing size instead of increasing

3. Consider the following Go code for a dynamic stack push operation:

func (s *Stack) Push(val int) {
  if s.size == len(s.data) {
    newData := make([]int, len(s.data)*2)
    copy(newData, s.data)
    s.data = newData
  }
  s.data[s.size] = val
  s.size++
}

stack := Stack{data: make([]int, 2), size: 0}
stack.Push(10)
stack.Push(20)
stack.Push(30)
fmt.Println(stack.data[:stack.size])

What is the output?

medium

A. [10 20]

B. [10 20 0]

C. [10 20 30]

D. runtime error: index out of range

Solution

1. Step 1: Trace initial stack state and pushes

   Initial data slice size is 2, size=0. Push 10 at index 0, size=1; Push 20 at index 1, size=2.

2. Step 2: Push 30 triggers resize

   Since size == len(data), create newData with size 4, copy old data, assign newData. Then add 30 at index 2, size=3.

3. Step 3: Print slice up to size

   Print data[:3] which contains [10 20 30].

4. Final Answer:

   [10 20 30] -> Option C

5. Quick Check:

   Resize + push = [10 20 30] [OK]

Hint: Resize before push when full, then add element [OK]

Common Mistakes:

• Forgetting to resize before push
• Printing full data slice including zeros
• Index out of range by pushing without resize

4. The following Go code for popping from a dynamic stack sometimes causes a runtime error. What is the bug?

func (s *Stack) Pop() int {
  s.size--
  val := s.data[s.size]
  if s.size < len(s.data)/4 {
    newData := make([]int, len(s.data)/2)
    copy(newData, s.data[:s.size])
    s.data = newData
  }
  return val
}

medium

A. Decreasing size before checking if stack is empty causes negative index.

B. Resizing array to half size before copying causes data loss.

C. Copying data after resizing causes runtime error.

D. Returning val before resizing causes stale value.

Solution

1. Step 1: Analyze size decrement before access

   Decreasing size before accessing data[s.size] can cause s.size to be negative if stack is empty.

2. Step 2: Understand runtime error cause

   Accessing data with negative index causes runtime panic (index out of range).

3. Final Answer:

   Decreasing size before checking if stack is empty causes negative index. -> Option A

4. Quick Check:

   Pop decrements size before check = negative index [OK]

Hint: Check empty before decrementing size [OK]

Common Mistakes:

• Not checking if stack is empty before pop
• Resizing array incorrectly
• Accessing data after size decrement without validation

5. You want to implement a dynamic stack in Go that shrinks its underlying array when the number of elements falls below one-fourth of the capacity, but never shrinks below a minimum capacity of 4. Which code snippet correctly implements this logic inside the Pop method?

hard

A. if s.size < len(s.data)/2 && len(s.data)/4 >= 4 { newData := make([]int, len(s.data)/4); copy(newData, s.data[:s.size]); s.data = newData }

B. if s.size < len(s.data)/4 { s.data = s.data[:len(s.data)/2] }

C. if s.size < 4 { s.data = make([]int, 4) }

D. if s.size < len(s.data)/4 && len(s.data)/2 >= 4 { newData := make([]int, len(s.data)/2); copy(newData, s.data[:s.size]); s.data = newData }

Solution

1. Step 1: Understand shrinking condition

   Shrink when size < 1/4 capacity, but only if new capacity ≥ 4.

2. Step 2: Check each option

   if s.size < len(s.data)/4 && len(s.data)/2 >= 4 { newData := make([]int, len(s.data)/2); copy(newData, s.data[:s.size]); s.data = newData } checks size < 1/4 capacity and new capacity ≥ 4, then resizes to half capacity correctly.

3. Final Answer:

   if s.size < len(s.data)/4 && len(s.data)/2 >= 4 { newData := make([]int, len(s.data)/2); copy(newData, s.data[:s.size]); s.data = newData } -> Option D

4. Quick Check:

   Shrink only if size < 1/4 and new capacity ≥ 4 [OK]

Hint: Shrink only if new capacity >= minimum size [OK]

Common Mistakes:

• Shrinking below minimum capacity
• Incorrect condition for shrinking
• Using wrong new capacity size