Array Insertion at Beginning in DSA Rust - 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.

Specifically, how the time grows as the array gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn insert_at_beginning(arr: &mut Vec<i32>, value: i32) {
    arr.insert(0, value);
}

This code inserts a new value at the start of a dynamic array (vector).

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Shifting all existing elements one position to the right.
• How many times: Once for each element already in the array.

How Execution Grows With Input

When the array has more items, more elements must move to make space at the start.

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

Pattern observation: The number of moves grows directly with the array size.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert at the start grows linearly with the number of elements.

Common Mistake

[X] Wrong: "Inserting at the beginning is always fast, like adding at the end."

[OK] Correct: Because all existing elements must move to make space, unlike adding at the end which is usually quick.

Interview Connect

Knowing this helps you explain why some data structures are better for front insertions, 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 a vector in Rust using insert(0, value)?

easy

A. The element is added at the end of the vector.

B. The element is added at the start, and all other elements shift right by one position.

C. The element replaces the first element without shifting others.

D. The vector size remains the same and no element is added.

Solution

1. Step 1: Understand insert(0, value) behavior

   In Rust, calling insert(0, value) on a vector adds the value at index 0.

2. Step 2: Effect on existing elements

   All existing elements shift one position to the right to make space for the new element.

3. Final Answer:

   The element is added at the start, and all other elements shift right by one position. -> Option B

4. Quick Check:

   Insert at index 0 shifts elements right [OK]

Hint: Insert at index 0 shifts all elements right [OK]

Common Mistakes:

• Thinking insert replaces the first element
• Assuming insert adds at the end
• Believing array size stays the same

2. Which of the following Rust code snippets correctly inserts the value 10 at the beginning of a vector named vec?

easy

A. vec.insert(0, 10);

B. vec.push(10);

C. vec[0] = 10;

D. vec.add(0, 10);

Solution

1. Step 1: Identify correct method for insertion at index

   Rust vectors use insert(index, value) to add elements at a specific position.

2. Step 2: Check each option

   vec.insert(0, 10); uses insert(0, 10), which inserts 10 at the start. vec.push(10); adds at the end. vec[0] = 10; replaces the first element without insertion. vec.add(0, 10); is invalid syntax.

3. Final Answer:

   vec.insert(0, 10); -> Option A

4. Quick Check:

   Use insert(0, value) to add at start [OK]

Hint: Use insert(0, value) to add at beginning [OK]

Common Mistakes:

• Using push() adds at end, not beginning
• Assigning vec[0] replaces element, no insertion
• Using non-existent method add()

3. What is the output of the following Rust code?

let mut vec = vec![2, 3, 4];
vec.insert(0, 1);
println!("{:?}", vec);

medium

A. [2, 3, 4, 1]

B. [2, 3, 4]

C. [1, 3, 4]

D. [1, 2, 3, 4]

Solution

1. Step 1: Initial vector state

   The vector starts as [2, 3, 4].

2. Step 2: Insert 1 at index 0

   Using vec.insert(0, 1) adds 1 at the start, shifting others right.

3. Final Answer:

   [1, 2, 3, 4] -> Option D

4. Quick Check:

   Insert at start shifts elements right [OK]

Hint: Insert at 0 adds element at front, shifts others right [OK]

Common Mistakes:

• Expecting element added at end
• Thinking insert replaces element
• Ignoring vector shift after insert

4. Identify the error in this Rust code:

let mut vec = vec![1, 2, 3];
vec.insert(5, 0);

medium

A. The index 5 is out of bounds for the vector of length 3.

B. The vector is immutable; it should be declared mutable.

C. The insert method parameters are reversed; index should be first, value second.

D. The insert method does not exist for vectors.

Solution

1. Step 1: Analyze the insert index

   The vector has length 3, valid insert indices are 0 to 3. Index 5 is out of bounds, causing runtime panic.

2. Step 2: Confirm syntax and mutability

   Parameters follow correct order insert(index, value); vector is declared mutable.

3. Final Answer:

   The index 5 is out of bounds for the vector of length 3. -> Option A

4. Quick Check:

   Insert index must be within vector bounds [OK]

Hint: Check insert(index, value) and index within vector length [OK]

Common Mistakes:

• Reversing insert parameters
• Using out-of-range index
• Forgetting to declare vector mutable

5. You have a vector vec = vec![10, 20, 30]. You want to insert multiple values [1, 2, 3] at the beginning efficiently. Which approach is best in Rust?

hard

A. Use a loop to insert each element at index 0 one by one.

B. Replace the original vector with the new elements only.

C. Create a new vector with the new elements, then extend it with the original vector.

D. Use vec.push() for each new element and then reverse the vector.

Solution

1. Step 1: Analyze inserting multiple elements at start

   Inserting one by one at index 0 shifts elements repeatedly, inefficient for multiple inserts.

2. Step 2: Efficient approach

   Create a new vector with new elements, then extend it with the original vector to combine efficiently.

3. Final Answer:

   Create a new vector with the new elements, then extend it with the original vector. -> Option C

4. Quick Check:

   Prepending by new vector + extend is efficient [OK]

Hint: Prepend multiple by new vector + extend original [OK]

Common Mistakes:

• Inserting elements one by one at index 0 (slow)
• Using push then reversing (extra steps)
• Replacing original vector loses data