Array Deletion at Middle Index in DSA Rust

Mental Model

To delete an element in the middle of an array, we shift all elements after it one step left to fill the gap.

Analogy: Imagine a row of chairs with people sitting. If one person leaves from the middle, everyone behind moves one seat forward to close the empty spot.

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

Dry Run Walkthrough

Input: array: [1, 2, 3, 4, 5], delete element at index 2

Goal: Remove the element at index 2 and shift remaining elements left

Step 1: Start deletion at index 2 (value 3)

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

Why: We identify the element to remove

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

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

Why: Fill the gap by moving next element left

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

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

Why: Continue shifting elements left

Step 4: Reduce array size by 1, ignoring last duplicate

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

Why: Remove the last duplicate element after shifting

Result:

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

Annotated Code

DSA Rust

fn delete_at_middle(arr: &mut Vec<i32>, index: usize) {
    if index >= arr.len() {
        return; // index out of bounds, do nothing
    }
    for i in index..arr.len() - 1 {
        arr[i] = arr[i + 1]; // shift element left
    }
    arr.pop(); // remove last duplicate element
}

fn main() {
    let mut arr = vec![1, 2, 3, 4, 5];
    delete_at_middle(&mut arr, 2);
    for val in &arr {
        print!("{} -> ", val);
    }
    println!("null");
}

if index >= arr.len() { return; }

guard against invalid index to avoid errors

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

shift elements left starting from deletion index

arr.pop();

remove last element which is now duplicate

Output

1 -> 2 -> 4 -> 5 -> null

Complexity Analysis

Time: O(n) because we may shift up to n-1 elements after the deleted index

Space: O(1) because deletion and shifting happen in place without extra storage

vs Alternative: Compared to creating a new array without the element (O(n) time and O(n) space), this method is more space efficient

Edge Cases

delete at index 0 (first element)

All elements shift left, first element removed

DSA Rust

if index >= arr.len() { return; }

delete at last index

No shifting needed, just pop last element

DSA Rust

if index == arr.len() - 1 { arr.pop(); return; }

delete with index out of bounds

Function returns immediately, no change

DSA Rust

if index >= arr.len() { return; }

When to Use This Pattern

When you need to remove an element from the middle of an array and keep order, use shifting to fill the gap because arrays have fixed positions.

Common Mistakes

Mistake: Not shifting elements after deletion index, leaving a gap
Fix: Shift all elements after the deleted index one position left

Mistake: Not reducing array size after shifting, causing duplicate last element
Fix: Remove the last element after shifting using pop()

Summary

Deletes an element at a given middle index by shifting subsequent elements left and reducing array size.

Use when you want to remove an element from an array and maintain the order of remaining elements.

The key insight is to shift elements left to fill the gap, then remove the last duplicate element.

Practice

1. What happens when you delete the middle element from an array with an odd number of elements?

easy

A. The array size remains the same but the middle element is set to zero.

B. The middle element is removed and the array size decreases by one.

C. The last element is removed instead of the middle element.

D. The array is reversed after deletion.

Solution

1. Step 1: Identify the middle index in an odd-length array

   The middle index is calculated as length divided by 2 (integer division).

2. Step 2: Remove the element at the middle index

   Deleting this element reduces the array size by one and shifts elements after it left.

3. Final Answer:

   The middle element is removed and the array size decreases by one. -> Option B

4. Quick Check:

   Deleting middle element shrinks array [OK]

Hint: Middle index = length / 2 for odd arrays [OK]

Common Mistakes:

• Thinking array size stays the same after deletion
• Removing last element instead of middle
• Not shifting elements after deletion

2. Which Rust code snippet correctly deletes the middle element from a vector v with odd length?

easy

A. v.pop(v.len() / 2);

B. v.delete(v.len() / 2);

C. v.remove(v.len() / 2);

D. v.erase(v.len() / 2);

Solution

1. Step 1: Identify Rust method to remove element by index

   Rust's Vec type uses remove(index) to delete element at given index.

2. Step 2: Calculate middle index and call remove

   Middle index is v.len() / 2. Calling v.remove(v.len() / 2) deletes middle element.

3. Final Answer:

   v.remove(v.len() / 2); -> Option C

4. Quick Check:

   Use remove(index) to delete element [OK]

Hint: Use Vec::remove(index) to delete element [OK]

Common Mistakes:

• Using non-existent methods like delete or erase
• Using pop which removes last element only
• Passing index to pop which takes no arguments

3. What is the output of this Rust code?

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

medium

A. [10, 30, 40, 50]

B. [10, 20, 30, 40]

C. [20, 30, 40, 50]

D. [10, 20, 40, 50]

Solution

1. Step 1: Calculate middle index of vector

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

2. Step 2: Remove element at index 2 and print vector

   Element at index 2 is 30, removed. Remaining vector is [10, 20, 40, 50].

3. Final Answer:

   [10, 20, 40, 50] -> Option D

4. Quick Check:

   Removed middle element 30, vector shrinks [OK]

Hint: Remove element at len()/2 index for middle deletion [OK]

Common Mistakes:

• Removing wrong index element
• Confusing index with value
• Expecting vector size unchanged

4. Identify the error in this Rust code that tries to delete the middle element of a vector v:

let mut v = vec![1, 2];
v.remove(v.len() / 2 + 1);
println!("{:?}", v);

medium

A. Index used for removal is off by one, causing panic.

B. Vector cannot be mutable for removal.

C. remove() method does not exist for vectors.

D. The println! macro is used incorrectly.

Solution

1. Step 1: Calculate middle index for even-length vector

   Vector length is 2, middle index should be 2 / 2 = 1.

2. Step 2: Check removal index used in code

   Code uses index 1 + 1 = 2, which is out of bounds.

3. Step 3: Understand consequences

   Index 2 >= length 2 causes runtime panic (out of bounds).

4. Final Answer:

   Index used for removal is off by one, causing panic. -> Option A

5. Quick Check:

   Use correct middle index = len()/2 [OK]

Hint: Middle index is len()/2, no +1 for removal [OK]

Common Mistakes:

• Adding +1 to middle index incorrectly
• Trying to remove from immutable vector
• Misusing remove method name

5. Given a vector v of even length, how can you delete the lower middle element (the one at index len()/2 - 1) and then print the updated vector in Rust?

hard

A. v.remove(v.len() / 2 - 1); println!("{:?}", v);

B. v.remove(v.len() / 2); println!("{:?}", v);

C. v.pop(); println!("{:?}", v);

D. v.remove(v.len() / 2 + 1); println!("{:?}", v);

Solution

1. Step 1: Identify lower middle index for even-length vector

   For even length, lower middle index is len()/2 - 1.

2. Step 2: Remove element at lower middle index and print vector

   Use v.remove(v.len() / 2 - 1) to delete lower middle element, then print with println!("{:?}", v);.

3. Final Answer:

   v.remove(v.len() / 2 - 1); println!("{:?}", v); -> Option A

4. Quick Check:

   Remove lower middle with len()/2 - 1 [OK]

Hint: For even length, lower middle = len()/2 - 1 [OK]

Common Mistakes:

• Removing upper middle instead of lower middle
• Using pop which removes last element
• Adding +1 to index incorrectly