Array Insertion at Beginning in DSA C++

Mental Model

To insert a new element at the start of an array, we must move all existing elements one step to the right to make space.

Analogy: Imagine a row of chairs with people sitting. To add a new person at the front, everyone must stand up and move one chair to the right, freeing the first chair.

Index: 0   1   2   3   4
Array: [1]->[2]->[3]->[4]->[5]
Insert new element '0' at index 0
After shift:
Array: [1]->[1]->[2]->[3]->[4]->[5]

Dry Run Walkthrough

Input: array: [1, 2, 3, 4, 5], insert value 0 at beginning

Goal: Insert 0 at the start and shift all elements right

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

[1]->[2]->[3]->[4]->[5]->[5]
Indexes: 0  1  2  3  4  5

Why: Make space at index 0 by moving last element right

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

[1]->[2]->[3]->[4]->[4]->[5]
Indexes: 0  1  2  3  4  5

Why: Continue shifting elements right to free index 0

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

[1]->[2]->[3]->[3]->[4]->[5]
Indexes: 0  1  2  3  4  5

Why: Keep shifting elements right

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

[1]->[2]->[2]->[3]->[4]->[5]
Indexes: 0  1  2  3  4  5

Why: Shift elements right to clear index 0

Step 5: Shift element at index 0 (1) to index 1

[1]->[1]->[2]->[3]->[4]->[5]
Indexes: 0  1  2  3  4  5

Why: Final shift to free index 0

Step 6: Insert new value 0 at index 0

[0]->[1]->[2]->[3]->[4]->[5]
Indexes: 0  1  2  3  4  5

Why: Place new element at the beginning

Result:

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

Annotated Code

DSA C++

#include <iostream>
using namespace std;

void insertAtBeginning(int arr[], int &size, int capacity, int value) {
    if (size >= capacity) {
        cout << "Array is full, cannot insert." << endl;
        return;
    }
    // Shift elements right to make space at index 0
    for (int i = size - 1; i >= 0; i--) {
        arr[i + 1] = arr[i]; // move element right
    }
    arr[0] = value; // insert new value at start
    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 << endl;
}

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

    insertAtBeginning(arr, size, capacity, value);
    printArray(arr, size);

    return 0;
}

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

move elements right starting from last to free index 0

arr[i + 1] = arr[i]; // move element right

shift element at i to i+1

arr[0] = value; // insert new value at start

place new element at beginning

size++; // increase size

update size after insertion

Output

0 -> 1 -> 2 -> 3 -> 4 -> 5

Complexity Analysis

Time: O(n) because we must shift all n elements one position to the right

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

vs Alternative: Compared to inserting at the end (O(1)), inserting at beginning requires shifting all elements, making it slower for large arrays

Edge Cases

empty array

insertion simply places the new element at index 0 without shifting

DSA C++

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

array full (size == capacity)

insertion is not performed and a message is printed

DSA C++

if (size >= capacity) {

single element array

the single element is shifted right and new element inserted at start

DSA C++

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

When to Use This Pattern

When you need to add an element at the start of a fixed-size array, expect to shift all elements right to make space.

Common Mistakes

Mistake: Shifting elements left to right instead of right to left causes overwriting data.
Fix: Always shift elements from the end towards the beginning to avoid overwriting.

Summary

Inserts a new element at the start of an array by shifting existing elements right.

Use when you need to add an element at the beginning of an array with fixed size.

The key insight is to shift elements from the end to avoid overwriting data.

Practice

1. What happens when you insert an element at the beginning of an array in C++?

easy

A. All existing elements shift one position to the right to make space.

B. The new element replaces the first element without shifting others.

C. The array size decreases by one.

D. The array elements are sorted automatically.

Solution

1. Step 1: Understand array structure

   An array stores elements in continuous memory locations.

2. Step 2: Effect of insertion at beginning

   To insert at the start, all elements must move right to free the first position.

3. Final Answer:

   All existing elements shift one position to the right to make space. -> Option A

4. Quick Check:

   Insertion at start shifts elements right = B [OK]

Hint: Insertion at start shifts elements right to free first slot [OK]

Common Mistakes:

• Thinking new element replaces first without shifting
• Assuming array size decreases
• Believing array sorts automatically

2. Which of the following is the correct syntax to insert an element `x` at the beginning of an array `arr` of size `n` in C++ (assuming enough space)?

easy

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

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

C. for(int i = n; i > 0; i--) arr[i] = arr[i-1]; arr[0] = x; n++;

D. arr[n] = x; n++;

Solution

1. Step 1: Shift elements right from end

   Loop from last index `n` down to 1, moving each element to the right by one.

2. Step 2: Insert new element at index 0 and increase size

   Place `x` at `arr[0]` and increment `n`.

3. Final Answer:

   for(int i = n; i > 0; i--) arr[i] = arr[i-1]; arr[0] = x; n++; -> Option C

4. Quick Check:

   Shift right from end, insert at 0 = C [OK]

Hint: Shift from end to start, then insert at zero index [OK]

Common Mistakes:

• Shifting from start to end overwrites data
• Not incrementing array size
• Inserting without shifting elements

3. What is the output of the following C++ code?

int arr[5] = {2, 4, 6, 8, 10};
int n = 5;
int x = 1;
for(int i = n; i > 0; i--) {
  arr[i] = arr[i-1];
}
arr[0] = x;
n++;
for(int i = 0; i < n; i++) {
  std::cout << arr[i] << " ";
}

medium

A. 2 4 6 8 10 1

B. 1 2 4 6 8 10

C. 1 2 4 6 8

D. 2 4 6 8 10

Solution

1. Step 1: Shift elements right to make space

   Elements move right: arr[5]=arr[4]=10, arr[4]=arr[3]=8, arr[3]=arr[2]=6, arr[2]=arr[1]=4, arr[1]=arr[0]=2.

2. Step 2: Insert 1 at arr[0] and print

   arr[0]=1, array becomes [1,2,4,6,8,10], printed with space.

3. Final Answer:

   1 2 4 6 8 10 -> Option B

4. Quick Check:

   Shift right + insert 1 at start = A [OK]

Hint: Shift right, insert new at zero, print all elements [OK]

Common Mistakes:

• Not shifting elements correctly
• Printing old array size
• Inserting at wrong index

4. Identify the error in this code snippet that inserts `x` at the beginning of array `arr` of size `n`:

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

medium

A. Loop shifts elements left instead of right, overwriting data.

B. Array size `n` is not incremented after insertion.

C. New element is inserted at wrong index.

D. Loop should start from `n` and go down to 1 to avoid overwrite.

Solution

1. Step 1: Analyze loop direction

   Loop moves from 0 to n-1, shifting elements forward, overwriting original data.

2. Step 2: Correct loop direction

   Loop must run backward from n to 1 to shift elements safely without overwrite.

3. Final Answer:

   Loop should start from `n` and go down to 1 to avoid overwrite. -> Option D

4. Quick Check:

   Backward loop prevents overwrite = D [OK]

Hint: Shift elements backward from end to start to avoid overwrite [OK]

Common Mistakes:

• Shifting elements forward overwrites data
• Forgetting to increment array size
• Inserting element at wrong position

5. Given an array `arr` of size `n` with elements sorted in ascending order, how can you insert a new element `x` at the beginning and keep the array sorted?

hard

A. If `x` is smaller than `arr[0]`, shift elements right and insert `x` at start; else find correct position.

B. Insert `x` at the beginning and then sort the entire array again.

C. Always insert `x` at the beginning without shifting elements.

D. Replace the last element with `x` if `x` is smaller than last element.

Solution

1. Step 1: Check if `x` is smaller than first element

   If yes, shift all elements right and insert `x` at index 0 to keep order.

2. Step 2: If `x` is not smallest, find correct position

   Find proper index to insert `x` to maintain sorted order, not necessarily at start.

3. Final Answer:

   If `x` is smaller than `arr[0]`, shift elements right and insert `x` at start; else find correct position. -> Option A

4. Quick Check:

   Insert at start only if smaller, else find position = A [OK]

Hint: Insert at start only if smaller; else find correct sorted position [OK]

Common Mistakes:

• Always inserting at start breaks sorting
• Sorting entire array after insertion wastes time
• Replacing last element loses data