Array Insertion at Middle Index in DSA C++

Mental Model

To insert a new value in the middle of an array, we shift all elements from the middle to the end one step to the right to make space.

Analogy: Imagine a row of chairs where you want to add a new person in the middle. Everyone from that spot to the end stands up and moves one chair to the right to free a seat.

Index: 0   1   2   3   4  
Array: [1]->[2]->[3]->[4]->[5]
Insert at index 2 (middle) ↑

Dry Run Walkthrough

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

Goal: Insert 99 at index 2 and shift elements right to keep all values

Step 1: Start shifting elements from the last index to index 2 one step right

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

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

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

[1]->[2]->[3]->[4]->[5]->[5]

Why: Shift last element right to free index 4

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

[1]->[2]->[3]->[4]->[4]->[5]

Why: Shift element at index 3 right to free index 3

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

[1]->[2]->[3]->[3]->[4]->[5]

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

Step 5: Insert 99 at index 2

[1]->[2]->[99]->[3]->[4]->[5]

Why: Place new value in the freed space

Result:

[1]->[2]->[99]->[3]->[4]->[5]

Annotated Code

DSA C++

#include <iostream>
using namespace std;

void insertAtMiddle(int arr[], int &size, int capacity, int value, int index) {
    if (size >= capacity || index > size || index < 0) {
        cout << "Insertion not possible\n";
        return;
    }
    // Shift elements right from the end to index
    for (int i = size - 1; i >= index; i--) {
        arr[i + 1] = arr[i]; // shift element right
    }
    arr[index] = value; // insert new value
    size++; // increase size
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i];
        if (i != size - 1) cout << " -> ";
    }
    cout << "\n";
}

int main() {
    int capacity = 10;
    int arr[10] = {1, 2, 3, 4, 5};
    int size = 5;
    int value = 99;
    int index = 2;

    insertAtMiddle(arr, size, capacity, value, index);
    printArray(arr, size);
    return 0;
}

for (int i = size - 1; i >= index; i--) { arr[i + 1] = arr[i]; }

Shift elements right from the end to index to make space

arr[index] = value;

Insert new value at the freed index

size++;

Increase size after insertion

Output

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

Complexity Analysis

Time: O(n) because in the worst case we shift half of the elements to the right

Space: O(1) because insertion is done in place without extra arrays

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

Edge Cases

Insert at index 0 (start)

All elements shift right, new value placed at start

DSA C++

if (size >= capacity || index > size || index < 0) {

Insert at index equal to size (end)

No shifting needed, new value appended

DSA C++

for (int i = size - 1; i >= index; i--) {

Array full (size == capacity)

Insertion rejected with message

DSA C++

if (size >= capacity || index > size || index < 0) {

When to Use This Pattern

When you need to add an element inside an array and keep order, use shifting to make space before insertion.

Common Mistakes

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

Summary

It inserts a new value at a given middle index by shifting elements right.

Use it when you want to add an element inside an array without losing existing data.

The key is to shift elements from the end towards the insertion point to free space.

Practice

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

easy

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

B. Replacing the middle element with a new one

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

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 right.

2. Step 2: Differentiate from other operations

   Replacing or removing elements is not insertion; adding at the end is not middle insertion.

3. Final Answer:

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

4. Quick Check:

   Middle insertion means insert and shift right [OK]

Hint: Middle insertion shifts elements right from center [OK]

Common Mistakes:

• Thinking insertion replaces the middle element
• Confusing insertion with appending at the end
• Assuming middle means removing element

2. Which of the following C++ code snippets correctly inserts an element `x` at the middle index of array `arr` of size `n`?

easy

A. arr[n] = x; for(int i = n/2; i < n; i++) arr[i] = arr[i+1];

B. for(int i = 0; i < n/2; i++) arr[i] = arr[i+1]; arr[n/2] = x;

C. arr[n/2] = x; for(int i = n/2; i < n; i++) arr[i+1] = arr[i];

D. for(int i = n; i > n/2; i--) arr[i] = arr[i-1]; arr[n/2] = x;

Solution

1. Step 1: Shift elements right from middle index

   Loop from end (n) down to middle (n/2 + 1) shifting elements right to make space.

2. Step 2: Insert element at middle index

   Assign new element x at index n/2 after shifting.

3. Final Answer:

   for(int i = n; i > n/2; i--) arr[i] = arr[i-1]; arr[n/2] = x; -> Option D

4. Quick Check:

   Shift right then insert at middle [OK]

Hint: Shift elements right from end to middle before insert [OK]

Common Mistakes:

• Shifting elements left instead of right
• Inserting before shifting elements
• Incorrect loop direction causing overwrite

3. What is the output array after inserting 99 at the middle index of arr = {10, 20, 30, 40, 50} using the correct insertion method?

medium

A. [10, 20, 30, 40, 99, 50]

B. [10, 20, 99, 30, 40, 50]

C. [10, 20, 30, 99, 40, 50]

D. [10, 20, 30, 40, 50, 99]

Solution

1. Step 1: Calculate middle index

   Array size n=5, middle index = n/2 = 2 (0-based indexing).

2. Step 2: Shift elements right and insert 99

   Shift elements from index 4 to 2 right by one position, then insert 99 at index 2.

3. Final Answer:

   [10, 20, 99, 30, 40, 50] -> Option B

4. Quick Check:

   Insert at index 2 shifts right [OK]

Hint: Middle index = size/2; shift right, then insert [OK]

Common Mistakes:

• Inserting at wrong index (like 3 or 4)
• Not shifting elements before insertion
• Appending at the end instead of middle

4. Identify the error in the following code snippet that inserts element `x` at the middle index of array `arr` of size `n`:

for(int i = n/2; i < n; i++) {
  arr[i+1] = arr[i];
}
arr[n/2] = x;

medium

A. Loop shifts elements left instead of right

B. Index out of bounds when accessing arr[i+1]

C. Loop direction causes overwriting elements

D. No error, code works correctly

Solution

1. Step 1: Analyze loop direction and effect

   The loop moves forward from middle to end, copying arr[i] to arr[i+1], overwriting elements before they are moved.

2. Step 2: Identify correct approach

   Elements must be shifted right starting from the end backward to avoid overwriting data.

3. Final Answer:

   Loop direction causes overwriting elements -> Option C

4. Quick Check:

   Shift right must go backward to avoid overwrite [OK]

Hint: Shift elements right backward from end to middle [OK]

Common Mistakes:

• Shifting elements forward causing data loss
• Ignoring array bounds when shifting
• Assuming forward loop works for shifting right

5. Given an array arr = {5, 10, 15, 20, 25, 30} of size 6, after inserting element 99 at the middle index, what will be the final array?

hard

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

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

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

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

Solution

1. Step 1: Calculate middle index for even-sized array

   Array size n=6, middle index = n/2 = 3 (0-based indexing).

2. Step 2: Shift elements right from index 5 to 3

   Shift elements at indices 5,4,3 one position right to make space at index 3.

3. Step 3: Insert 99 at middle index

   Place 99 at index 3 after shifting.

4. Final Answer:

   [5, 10, 15, 99, 20, 25, 30] -> Option A

5. Quick Check:

   Insert at index 3 shifts right [OK]

Hint: For even size, middle = size/2; shift right, then insert [OK]

Common Mistakes:

• Inserting at index 2 instead of 3
• Not shifting elements before insertion
• Appending at the end instead of middle