Array Insertion at Middle Index in DSA Rust

Mental Model

To insert a new item in the middle of an array, we make space by moving all items after the middle one step to the right.

Analogy: Imagine a row of chairs where you want to add a new person in the middle. You ask everyone from the middle to the end to stand up and move one chair to the right, so the middle chair becomes free for the new person.

Index: 0   1   2   3   4
Array: [1]->[2]->[3]->[4]->[5]

Dry Run Walkthrough

Input: array: [1, 2, 3, 4, 5], insert value 99 at middle index 2

Goal: Insert 99 at index 2 and shift elements after index 2 to the right

Step 1: Identify middle index 2 for insertion

Index: 0   1   2   3   4
Array: [1]->[2]->[3]->[4]->[5]

Why: We need to insert at index 2, so we prepare to shift elements from index 2 onwards

Step 2: Shift element at index 4 (5) to index 5

Index: 0   1   2   3   4   5
Array: [1]->[2]->[3]->[4]->[5]->[5]

Why: Make space at index 5 by moving last element one step right

Step 3: Shift element at index 3 (4) to index 4

Index: 0   1   2   3   4   5
Array: [1]->[2]->[3]->[4]->[4]->[5]

Why: Continue shifting elements right to free index 4

Step 4: Shift element at index 2 (3) to index 3

Index: 0   1   2   3   4   5
Array: [1]->[2]->[3]->[3]->[4]->[5]

Why: Shift element at insertion index to the right to free index 2

Step 5: Insert 99 at index 2

Index: 0   1   2   3   4   5
Array: [1]->[2]->[99]->[3]->[4]->[5]

Why: Place new value at the freed middle index

Result:

Index: 0   1   2   3   4   5
Array: [1]->[2]->[99]->[3]->[4]->[5]

Annotated Code

DSA Rust

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

fn main() {
    let mut arr = vec![1, 2, 3, 4, 5];
    insert_middle(&mut arr, 99);
    for v in &arr {
        print!("{} -> ", v);
    }
    print!("null\n");
}

let mid = arr.len() / 2;

Calculate middle index for insertion

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

Expand array size by one to make space

for i in (mid..arr.len()-1).rev() {

Loop backwards from last element to middle to shift elements right

arr[i + 1] = arr[i]; // shift elements right

Move each element one position to the right

arr[mid] = val; // insert new value

Place new value at middle index

Output

1 -> 2 -> 99 -> 3 -> 4 -> 5 -> null

Complexity Analysis

Time: O(n) because we may need to shift up to half of the elements to the right

Space: O(1) because insertion is done in place with only one extra space for push

vs Alternative: Compared to creating a new array and copying elements, this in-place shift saves space but still requires shifting elements, which is slower than appending at the end

Edge Cases

empty array

Inserts at index 0 without shifting

DSA Rust

let mid = arr.len() / 2;

array with one element

Inserts new element at index 0 (middle), shifts existing element right

DSA Rust

for i in (mid..arr.len()-1).rev() {

array with even length

Inserts at lower middle index (len/2), shifting elements after it

DSA Rust

let mid = arr.len() / 2;

When to Use This Pattern

When you need to insert an element inside an array and not at the end, especially at the middle, use the shifting pattern to make space by moving elements right.

Common Mistakes

Mistake: Not increasing array size before shifting elements, causing overwrite or panic
Fix: Always push a dummy element first to increase size before shifting

Mistake: Shifting elements from left to right causing data overwrite
Fix: Shift elements from right to left (backwards) to avoid overwriting data

Summary

Inserts a new value at the middle index of an array by shifting elements to the right.

Use when you want to add an element inside an array, not just at the end.

The key is to shift elements from the end towards the middle to make space without losing data.

Practice

1. What does inserting an element at the middle index of an array mean?

easy

A. Adding a new element at the end of the array

B. Replacing the middle element with a new one

C. Adding a new element exactly in the center, shifting others right

D. Removing the middle element from the array

Solution

1. Step 1: Understand middle index insertion

   Inserting at the middle means placing a new element at the center position, pushing existing elements to the right.

2. Step 2: Differentiate from other operations

   Replacing or removing elements changes existing data, but insertion adds a new element without deletion.

3. Final Answer:

   Adding a new element exactly in the center, shifting others right -> Option C

4. Quick Check:

   Middle insertion means add and shift [OK]

Hint: Middle insertion adds element, shifts others right [OK]

Common Mistakes:

• Thinking insertion replaces an element
• Confusing insertion with removal
• Assuming insertion always happens at end

2. Which Rust code correctly inserts the value 99 at the middle index of a vector named vec?

easy

A. vec.insert(vec.len() / 2, 99);

B. vec.push(99);

C. vec[vec.len() / 2] = 99;

D. vec.remove(vec.len() / 2); vec.push(99);

Solution

1. Step 1: Identify correct insertion method

   Rust's insert method adds an element at a given index, shifting others right.

2. Step 2: Calculate middle index and apply insert

   Using vec.len() / 2 gives the middle index; vec.insert places 99 there correctly.

3. Final Answer:

   vec.insert(vec.len() / 2, 99); -> Option A

4. Quick Check:

   Use insert with middle index [OK]

Hint: Use vec.insert(middle_index, value) to insert [OK]

Common Mistakes:

• Using push adds at end, not middle
• Assigning with vec[index] replaces, not inserts
• Removing then pushing changes order

3. What is the output of this Rust code?

let mut vec = vec![10, 20, 30, 40];
vec.insert(vec.len() / 2, 25);
println!("{:?}", vec);

medium

A. [10, 20, 30, 25, 40]

B. [10, 20, 25, 30, 40]

C. [10, 25, 20, 30, 40]

D. [25, 10, 20, 30, 40]

Solution

1. Step 1: Calculate middle index

   Vector length is 4, so middle index is 4 / 2 = 2.

2. Step 2: Insert 25 at index 2

   Inserting 25 at index 2 shifts elements at and after index 2 right: 30 and 40 move right.

3. Final Answer:

   [10, 20, 25, 30, 40] -> Option B

4. Quick Check:

   Insert at middle shifts elements right [OK]

Hint: Middle index = length/2; insert shifts right [OK]

Common Mistakes:

• Inserting at wrong index
• Confusing insert with replace
• Miscounting vector length

4. Identify the error in this Rust code that tries to insert 50 at the middle of vec:

let mut vec = vec![1, 2, 3, 4, 5];
let mid = vec.len() / 2;
vec[mid] = 50;
println!("{:?}", vec);

medium

A. Using assignment replaces element instead of inserting

B. vec.len() / 2 is incorrect middle index

C. vec is immutable, cannot modify

D. println! syntax is wrong

Solution

1. Step 1: Understand vec[mid] = 50;

   This replaces the element at index mid instead of inserting a new one.

2. Step 2: Correct method is insert

   To insert, use vec.insert(mid, 50); which shifts elements right.

3. Final Answer:

   Using assignment replaces element instead of inserting -> Option A

4. Quick Check:

   Assignment replaces, insert adds [OK]

Hint: Use insert() to add, not assignment [OK]

Common Mistakes:

• Replacing element instead of inserting
• Misunderstanding vector mutability
• Incorrect println! usage

5. Given a vector vec = vec![5, 10, 15, 20, 25, 30], write Rust code to insert 17 exactly in the middle so that the vector remains sorted. What will be the vector after insertion?

hard

A. [5, 10, 15, 20, 25, 30, 12]

B. [5, 10, 15, 12, 20, 25, 30]

C. [12, 5, 10, 15, 20, 25, 30]

D. [5, 10, 15, 17, 20, 25, 30]

Solution

1. Step 1: Find middle index for insertion

   Vector length is 6, middle index is 6 / 2 = 3.

2. Step 2: Insert 17 at index 3 to keep sorted order

   Inserting 17 at index 3 shifts elements 20, 25, 30 right, keeping order.

3. Final Answer:

   [5, 10, 15, 17, 20, 25, 30] -> Option D

4. Quick Check:

   Insert 17 at middle index 3 to keep sorted [OK]

Hint: Insert at length/2 to keep sorted vector [OK]

Common Mistakes:

• Inserting at wrong index breaking order
• Appending instead of inserting
• Replacing element instead of inserting