Array Insertion at Beginning in DSA Go - Time & Space Complexity

Time Complexity: Array Insertion at Beginning

O(n)

Understanding Time Complexity

We want to understand how long it takes to add an item at the start of an array.

How does the time needed change as the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

package main

func insertAtBeginning(arr []int, val int) []int {
    arr = append(arr, 0)           // increase slice size by 1
    for i := len(arr) - 1; i > 0; i-- {
        arr[i] = arr[i-1]          // shift elements right
    }
    arr[0] = val                   // insert new value at start
    return arr
}

This code adds a new value at the start by shifting all existing elements one step to the right.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that shifts elements one by one to the right.
• How many times: It runs once for each element already in the array (n times).

How Execution Grows With Input

As the array grows, the number of shifts grows the same way.

Input Size (n)	Approx. Operations
10	About 10 shifts
100	About 100 shifts
1000	About 1000 shifts

Pattern observation: The work grows directly with the number of elements; double the elements, double the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert at the beginning grows linearly with the array size.

Common Mistake

[X] Wrong: "Inserting at the start is always fast because we just add one item."

[OK] Correct: We must move all existing items to make space, so the bigger the array, the more moves needed.

Interview Connect

Knowing this helps you explain why some data structures are better for front insertions than arrays, showing your understanding of efficiency.

Self-Check

"What if we used a linked list instead of an array? How would the time complexity change?"

Practice

1. What happens when you insert an element at the beginning of an array in Go?

easy

A. The array size decreases by one.

B. The new element replaces the first element without shifting others.

C. All existing elements shift one position to the right to make space.

D. The new element is added at the end of the array.

Solution

1. Step 1: Understand array behavior in Go

   Arrays have fixed size, so to insert at the beginning, elements must shift right.

2. Step 2: Effect of insertion at beginning

   The first element moves to second position, second to third, and so on, making space at index 0.

3. Final Answer:

   All existing elements shift one position to the right to make space. -> Option C

4. Quick Check:

   Insertion at start shifts elements right = A [OK]

Hint: Insertion at start shifts all elements right by one [OK]

Common Mistakes:

• Thinking new element replaces first without shifting
• Assuming array size changes automatically
• Adding element at the end instead of beginning

2. Which of the following Go code snippets correctly inserts an element `x` at the beginning of a slice `s`?

easy

A. s = s[1:]

B. s = append(s, x)

C. s[0] = x

D. s = append([]int{x}, s...)

Solution

1. Step 1: Understand slice append syntax

   Appending a slice to another uses append(slice1, slice2...), so to add at start, prepend with new slice.

2. Step 2: Analyze each option

   s = append([]int{x}, s...) prepends x correctly; B appends at end; C replaces first element; D slices off first element.

3. Final Answer:

   s = append([]int{x}, s...) -> Option D

4. Quick Check:

   Prepend with append([]int{x}, s...) = A [OK]

Hint: Use append with new slice and ... to insert at start [OK]

Common Mistakes:

• Using append(s, x) adds at end, not start
• Replacing element instead of inserting
• Slicing removes elements instead of adding

3. What is the output of this Go code?

package main
import "fmt"
func main() {
  s := []int{2, 3, 4}
  s = append([]int{1}, s...)
  fmt.Println(s)
}

medium

A. [1 2 3 4]

B. [2 3 4 1]

C. [1 3 4]

D. [2 3 4]

Solution

1. Step 1: Initial slice and append operation

   Initial slice s is [2 3 4]. append([]int{1}, s...) adds 1 at start.

2. Step 2: Resulting slice after append

   New slice becomes [1 2 3 4] because 1 is prepended before all elements.

3. Final Answer:

   [1 2 3 4] -> Option A

4. Quick Check:

   Prepending 1 to [2 3 4] = [1 2 3 4] [OK]

Hint: append([]int{x}, s...) prepends x to slice s [OK]

Common Mistakes:

• Thinking append adds at end by default
• Ignoring ... operator to expand slice
• Confusing slice contents after append

4. Identify the error in this Go code that tries to insert 0 at the beginning of slice `s`:

package main
import "fmt"
func main() {
  s := []int{1, 2, 3}
  s[0] = 0
  fmt.Println(s)
}

medium

A. It replaces the first element instead of inserting a new one.

B. It causes a runtime panic due to index out of range.

C. It appends 0 at the end instead of the beginning.

D. It creates a new slice with 0 at the start.

Solution

1. Step 1: Analyze the assignment s[0] = 0

   This replaces the value at index 0 with 0, not inserting a new element.

2. Step 2: Effect on slice length and contents

   Slice length stays same; no shifting occurs; original first element lost.

3. Final Answer:

   It replaces the first element instead of inserting a new one. -> Option A

4. Quick Check:

   Assignment replaces element, does not insert [OK]

Hint: Assignment replaces element; use append to insert [OK]

Common Mistakes:

• Thinking s[0] = 0 inserts element
• Expecting slice length to increase
• Confusing replace with insert

5. Given a slice `s := []int{3, 4, 5}`, write Go code to insert the numbers 1 and 2 at the beginning so that the final slice is `[1 2 3 4 5]`. Which code snippet achieves this correctly?

hard

A. s[0], s[1] = 1, 2

B. s = append([]int{1, 2}, s...)

C. s = append(s[:0], 1, 2)

D. s = append(s, 1, 2)

Solution

1. Step 1: Understand slice prepending with append

   To add multiple elements at start, create a new slice with them and append original slice after.

2. Step 2: Analyze options

   s = append([]int{1, 2}, s...) prepends [1, 2] correctly; A replaces first two elements; B appends at end; C overwrites start without preserving rest.

3. Final Answer:

   s = append([]int{1, 2}, s...) -> Option B

4. Quick Check:

   Prepend multiple elements with append([]int{...}, s...) [OK]

Hint: Use append with slice of new elements and ... to prepend [OK]

Common Mistakes:

• Appending instead of prepending
• Overwriting elements without shifting
• Misusing slice syntax causing data loss