Stack Implementation Using Array in DSA Go - Time & Space Complexity

Time Complexity: Stack Implementation Using Array

O(1)

Understanding Time Complexity

We want to understand how fast stack operations run when using an array.

How does the time to push or pop items change as the stack grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

package main

import "fmt"

type Stack struct {
  items []int
}

func (s *Stack) Push(val int) {
  s.items = append(s.items, val)
}

func (s *Stack) Pop() int {
  if len(s.items) == 0 {
    return -1
  }
  val := s.items[len(s.items)-1]
  s.items = s.items[:len(s.items)-1]
  return val
}

func main() {
  s := Stack{}
  s.Push(10)
  s.Push(20)
  fmt.Println(s.Pop())
}

This code shows a stack using an array where we add (push) and remove (pop) items at the end.

Identify Repeating Operations

Look at the main repeated actions:

• Primary operation: Adding or removing an item at the end of the array.
• How many times: Each push or pop happens once per call, no loops inside.

How Execution Grows With Input

Each push or pop takes about the same time no matter how many items are in the stack.

Input Size (n)	Approx. Operations
10	10 pushes = 10 operations
100	100 pushes = 100 operations
1000	1000 pushes = 1000 operations

Pattern observation: Time grows linearly with number of operations, but each operation is constant time.

Final Time Complexity

Time Complexity: O(1)

This means each push or pop runs in constant time, no matter how big the stack is.

Common Mistake

[X] Wrong: "Push or pop takes longer as the stack grows because the array is bigger."

[OK] Correct: We only add or remove at the end, so no need to move other items. The operation stays quick.

Interview Connect

Knowing that stack operations are constant time helps you explain why stacks are efficient for many tasks like undo or expression evaluation.

Self-Check

"What if we changed the stack to add or remove items at the start of the array? How would the time complexity change?"

Practice

1. What is the main purpose of using an array to implement a stack?

easy

A. To sort elements automatically

B. To store elements in a first-in, first-out (FIFO) order

C. To store elements in a last-in, first-out (LIFO) order

D. To allow random access to elements

Solution

1. Step 1: Understand stack behavior

   A stack stores elements so the last added is the first removed, called LIFO.

2. Step 2: Role of array in stack

   An array holds elements in order, supporting push/pop at one end to maintain LIFO.

3. Final Answer:

   To store elements in a last-in, first-out (LIFO) order -> Option C

4. Quick Check:

   Stack = LIFO [OK]

Hint: Stack means last-in, first-out order [OK]

Common Mistakes:

• Confusing stack with queue (FIFO)
• Thinking array sorts elements automatically
• Assuming random access is main stack feature

2. Which of the following is the correct way to declare a stack using an array in Go?

easy

A. stack := []int{}

B. stack := array int

C. var stack [10]int

D. var stack int[]

Solution

1. Step 1: Understand Go slice declaration

   In Go, slices are dynamic arrays declared as []type{}, e.g., []int{}.

2. Step 2: Check options for correct syntax

   stack := []int{} uses correct slice literal syntax to create an empty int slice.

3. Final Answer:

   stack := []int{} -> Option A

4. Quick Check:

   Go slice syntax = []type{} [OK]

Hint: Use slice literal []int{} to declare empty stack [OK]

Common Mistakes:

• Using array keyword incorrectly
• Wrong order of type and brackets
• Declaring fixed size array instead of slice

3. What will be the output of the following Go code snippet implementing a stack push and pop?

package main
import "fmt"
func main() {
  stack := []int{}
  stack = append(stack, 10)
  stack = append(stack, 20)
  top := stack[len(stack)-1]
  stack = stack[:len(stack)-1]
  fmt.Println(top)
  fmt.Println(stack)
}

medium

A. 10
[]

B. 20
[10]

C. 20
[10 20]

D. 10
[20]

Solution

1. Step 1: Trace push operations

   stack starts empty, append 10 -> [10], append 20 -> [10, 20]

2. Step 2: Trace pop operation

   top = last element = 20, then remove last element -> stack becomes [10]

3. Final Answer:

   20 [10] -> Option B

4. Quick Check:

   Pop returns 20, stack left with 10 [OK]

Hint: Pop returns last pushed element, stack shrinks [OK]

Common Mistakes:

• Printing stack before pop
• Confusing first element with last
• Not slicing stack correctly after pop

4. Identify the error in this Go code snippet for stack push operation:

package main
func main() {
  var stack []int
  stack[len(stack)] = 5
}

medium

A. Index out of range error

B. Syntax error: missing import

C. No error, code runs fine

D. Type mismatch error

Solution

1. Step 1: Understand slice indexing

   Accessing stack[len(stack)] tries to assign beyond current slice length, causing error.

2. Step 2: Correct push uses append

   To add element, use append(stack, 5) instead of direct index assignment.

3. Final Answer:

   Index out of range error -> Option A

4. Quick Check:

   Assigning at len(slice) causes index error [OK]

Hint: Use append to add elements, not direct index [OK]

Common Mistakes:

• Trying to assign at slice length index
• Forgetting to import fmt (not needed here)
• Assuming slice auto-expands on index assignment

5. Given a stack implemented using an array in Go, how would you modify the pop operation to safely handle popping from an empty stack without causing a runtime error?

hard

A. Replace the stack with a map to avoid empty pop errors

B. Always pop without checking; Go handles empty slices gracefully

C. Use a for loop to pop all elements at once

D. Check if stack length is zero before popping and return an error or zero value

Solution

1. Step 1: Understand pop risk on empty stack

   Popping from empty slice causes index out of range runtime error.

2. Step 2: Add length check before pop

   Check if len(stack) == 0; if yes, return error or zero value to avoid crash.

3. Final Answer:

   Check if stack length is zero before popping and return an error or zero value -> Option D

4. Quick Check:

   Empty stack pop needs length check [OK]

Hint: Always check stack length before pop to avoid errors [OK]

Common Mistakes:

• Ignoring empty stack check causing runtime panic
• Using map instead of array unnecessarily
• Trying to pop all elements in a loop without condition