Array Insertion at Middle Index in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

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

It means adding a new element exactly in the center position of the array, shifting the elements after it one position to the right.

beginner

How do you find the middle index of an array with an even number of elements?

You divide the length of the array by 2. For example, if the array length is 6, the middle index is 3 (0-based indexing).

beginner

Why do we need to shift elements when inserting in the middle of an array?

Because arrays have fixed positions, to insert a new element in the middle, we move all elements from the middle to the end one step right to make space.

intermediate

What is the time complexity of inserting an element at the middle of an array?

The time complexity is O(n) because we may need to shift up to half of the elements to the right.

intermediate

In Rust, which data structure is more efficient for frequent insertions in the middle: Vec or LinkedList?

LinkedList is more efficient for frequent insertions in the middle because it does not require shifting elements like Vec does.

What is the middle index of an array with 7 elements (0-based indexing)?

A 3

B 4

C 2

D 5

The middle index is length divided by 2, so 7 / 2 = 3 (integer division).

When inserting an element at the middle of an array, what must happen to the elements after the middle?

A They are removed

B They stay in place

C They shift one position to the left

D They shift one position to the right

Elements after the middle must shift right to make space for the new element.

What is the time complexity of inserting an element at the middle of a Rust Vec?

A O(log n)

B O(n)

C O(1)

D O(n log n)

Insertion in the middle requires shifting elements, so it takes O(n) time.

Which Rust method can insert an element at a specific index in a Vec?

A push()

B pop()

C insert()

D append()

The insert() method inserts an element at a given index.

If you insert an element at the middle of an empty array, what happens?

A Element is added at index 0

B Error occurs

C Element is added at index 1

D Nothing happens

Inserting in an empty array adds the element at index 0.

Explain step-by-step how to insert an element at the middle index of an array.

Think about how to make space for the new element.

Describe the difference in performance when inserting in the middle of a Vec versus a LinkedList in Rust.

Consider how elements are stored and accessed.

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