Insert at Position 3 by Shifting Right

Position 3 targets index 2, but insertion also needs an unused slot

The position x = 3 means that 9 must become the third element. Because array indices start at 0, the target index is x - 1, which is 2. The existing values at indices 2 and 3 must move right, so the storage also needs one free index. Here, n = 4 and capacity = 5, leaving index 4 unused.

int target = x - 1;  // 2
int freeIndex = n;    // 4

An insertion at position x is valid when x is from 1 through n + 1. Position 1 inserts before the current first element, while position n + 1 inserts after the current last element. For this array, x = 3 is valid, and n < capacity confirms that one more value can fit.

A right shift must start at the occupied end

To open index 2, copy the last occupied value first. Set a[4] = a[3], which moves 1 into the unused slot. Then set a[3] = a[2], which moves 7 one position right. The original 1 is already safe at index 4 when index 3 changes.

Initial:       [4, 2, 7, 1, _]
a[4] = a[3]    [4, 2, 7, 1, 1]
a[3] = a[2]    [4, 2, 7, 7, 1]

Moving in the other direction destroys a source before you copy it. If you begin with a[3] = a[2], the array becomes [4, 2, 7, 7, _], so the original 1 at index 3 is gone. The later assignment a[4] = a[3] can copy only 7, not the lost 1.

The new value is written only after index 2 is open

After the two backward copies, the temporary state is [4, 2, 7, 7, 1]. Index 2 still contains the old 7, but the values that were at indices 2 and 3 now have safe copies to their right. Assign 9 to index 2 only now, producing [4, 2, 9, 7, 1].

for (int i = n; i > target; --i) {
    a[i] = a[i - 1];
}
a[target] = 9;
n++;

The logical size remains 4 while the copies and the new assignment happen. Increase n from 4 to 5 only after the insertion succeeds. The storage then contains five logical elements, [4, 2, 9, 7, 1], and n correctly describes how many elements can be read.

for (int i = n; i > x - 1; --i) {
    ________
}

Only the suffix beginning at position 3 has to move

The prefix [4, 2] is before position 3, so it stays unchanged. The original suffix [7, 1] contains two elements that must move right to make room for 9. The backward loop performs exactly two copies, one for each element in that suffix.

In general, the suffix beginning at position x contains n - x + 1 elements, so insertion takes O(n - x + 1) time. For x = 3 and n = 4, that is O(2), which is constant for this fixed input but grows with the suffix length. The direct assignments use O(1) extra space because they need no second array.