Array Insertion at Beginning in DSA Rust - Execution Trace

Concept Flow - Array Insertion at Beginning

Check if array has space

Yes↓

Shift elements right by 1

↓

Insert new element at index 0

↓

Done

To insert at the beginning, first check space, then shift all elements right to make room, and finally place the new element at index 0.

Execution Sample

DSA Rust

let mut arr = [1, 2, 3, 0, 0];
let mut size = 3;
let new_val = 9;
// Insert at beginning
for i in (0..size).rev() {
    arr[i + 1] = arr[i];
}
arr[0] = new_val;
size += 1;

This code inserts 9 at the start of an array with initial elements 1, 2, 3 by shifting elements right.

Execution Table

Step	Operation	Index i	Array State	Pointer Changes	Visual State
1	Start insertion	-	[1, 2, 3, 0, 0]	size=3	1 -> 2 -> 3 -> _ -> _
2	Shift element right	2	[1, 2, 3, 3, 0]	arr[3] = arr[2]	1 -> 2 -> 3 -> 3 -> _
3	Shift element right	1	[1, 2, 2, 3, 0]	arr[2] = arr[1]	1 -> 2 -> 2 -> 3 -> _
4	Shift element right	0	[1, 1, 2, 3, 0]	arr[1] = arr[0]	1 -> 1 -> 2 -> 3 -> _
5	Insert new_val at index 0	0	[9, 1, 2, 3, 0]	arr[0] = 9	9 -> 1 -> 2 -> 3 -> _
6	Insertion complete	-	[9, 1, 2, 3, 0]	size=4	9 -> 1 -> 2 -> 3 -> _

💡 All elements shifted right, new element inserted at index 0, size updated to 4

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
arr	[1, 2, 3, 0, 0]	[1, 2, 3, 3, 0]	[1, 2, 2, 3, 0]	[1, 1, 2, 3, 0]	[9, 1, 2, 3, 0]	[9, 1, 2, 3, 0]
size	3	3	3	3	3	4
new_val	9	9	9	9	9	9

Key Moments - 3 Insights

Why do we shift elements from the end towards the beginning, not the other way?

Shifting from the end (index 2 to 0) prevents overwriting elements before they are moved, as shown in steps 2 to 4 in the execution_table.

What happens if the array is full and we try to insert at the beginning?

If the array is full, shifting elements right would overwrite the last element or cause an error. The code assumes space is available, as checked in step 1.

Why do we update the size only after insertion?

Size updates after insertion (step 6) to reflect the new number of valid elements, ensuring the array state matches the logical size.

Visual Quiz - 3 Questions

Look at the execution_table, what is the array state after shifting the element at index 1?

A [1, 2, 2, 3, 0]

B [1, 1, 2, 3, 0]

C [1, 2, 3, 3, 0]

D [9, 1, 2, 3, 0]

💡 Hint

Check the row with Step 3 in the execution_table showing the array after shifting index 1.

At which step does the new value get inserted at the beginning?

A Step 4

B Step 3

C Step 5

D Step 6

💡 Hint

Look for the operation 'Insert new_val at index 0' in the execution_table.

If the initial size was 4 instead of 3, how would the shifting steps change?

A Shifting would start from index 2 as before

B There would be one more shift step starting from index 3

C No shifting needed, just insert at index 0

D Array would shrink automatically

💡 Hint

Consider how the loop runs from size-1 down to 0 in the code and how many elements need shifting.

Concept Snapshot

Array Insertion at Beginning:
- Check if space is available
- Shift all elements right from end to start
- Insert new element at index 0
- Update size to reflect new element
- Shifting prevents overwriting existing data

Full Transcript

To insert an element at the beginning of an array, first ensure there is space. Then, starting from the last valid element, shift each element one position to the right to make room. After shifting, place the new element at index zero. Finally, update the size to include the new element. This process avoids overwriting data by shifting from the end backwards.

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