Array Insertion at Beginning in DSA Rust

Mental Model

To insert a new item at the start of an array, we move all existing items one step to the right to make space.

Analogy: Imagine a row of chairs where a new person wants to sit at the first chair, so everyone shifts one chair to the right to make room.

Before insertion:
[1] -> [2] -> [3] -> null

After insertion of 0 at beginning:
[0] -> [1] -> [2] -> [3] -> null

Dry Run Walkthrough

Input: array: [1, 2, 3], insert value 0 at beginning

Goal: Insert 0 at the start and shift all elements right

Step 1: Start shifting elements from the end to the right

[1] -> [2] -> [3] -> null

Why: We need to move elements to make space at index 0

Step 2: Move element at index 2 (3) to index 3

[1] -> [2] -> [3] -> [3] (duplicate temporarily)

Why: Shift last element right to free index 2

Step 3: Move element at index 1 (2) to index 2

[1] -> [2] -> [2] -> [3]

Why: Shift next element right to free index 1

Step 4: Move element at index 0 (1) to index 1

[1] -> [1] -> [2] -> [3]

Why: Shift first element right to free index 0

Step 5: Insert new value 0 at index 0

[0] -> [1] -> [2] -> [3]

Why: Place new element at the beginning

Result:

[0] -> [1] -> [2] -> [3]

Annotated Code

DSA Rust

fn insert_at_beginning(arr: &mut Vec<i32>, val: i32) {
    arr.push(0); // increase size by one
    for i in (1..arr.len()).rev() {
        arr[i] = arr[i - 1]; // shift elements right
    }
    arr[0] = val; // insert new value at start
}

fn main() {
    let mut arr = vec![1, 2, 3];
    insert_at_beginning(&mut arr, 0);
    for v in &arr {
        print!("{} ", v);
    }
    println!();
}

arr.push(0); // increase size by one

Expand array size to make room for new element

for i in (1..arr.len()).rev() { arr[i] = arr[i - 1]; // shift elements right }

Shift all elements one position to the right starting from the end

arr[0] = val; // insert new value at start

Place the new value at the beginning of the array

Output

0 1 2 3 

Complexity Analysis

Time: O(n) because we shift all n elements one step to the right

Space: O(1) because we modify the array in place without extra storage

vs Alternative: Compared to appending at the end which is O(1), inserting at beginning requires shifting all elements, making it slower

Edge Cases

empty array

The new value is simply added as the only element

DSA Rust

arr.push(0); // increase size by one

array with one element

The single element is shifted right and new value inserted at start

DSA Rust

for i in (1..arr.len()).rev() { arr[i] = arr[i - 1]; }

When to Use This Pattern

When you need to add an element at the start of a fixed-size list and must keep order, use shifting to make space.

Common Mistakes

Mistake: Not increasing array size before shifting elements
Fix: Use arr.push(0) to expand array before shifting

Mistake: Shifting elements from start to end causing overwrite
Fix: Shift elements from end to start to avoid overwriting data

Summary

It inserts a new element at the start by shifting all existing elements right.

Use it when you must add an item at the beginning of an array and keep order.

The key is to shift elements from the end backward to avoid overwriting.

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