Array Deletion at Middle Index in DSA C - Time & Space Complexity

Time Complexity: Array Deletion at Middle Index

O(n)

Understanding Time Complexity

When we delete an element from the middle of an array, the time it takes depends on how many elements need to move.

We want to know how the work grows as the array gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void deleteMiddle(int arr[], int *size, int mid) {
    for (int i = mid; i < *size - 1; i++) {
        arr[i] = arr[i + 1];
    }
    (*size)--;
}
    

This code deletes the element at the middle index by shifting all elements after it one step left.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop shifting elements left after the middle index.
• How many times: It runs from the middle index to the end of the array, about half the array size.

How Execution Grows With Input

As the array size grows, the number of elements to shift grows roughly in half.

Input Size (n)	Approx. Operations
10	About 5 shifts
100	About 50 shifts
1000	About 500 shifts

Pattern observation: The work grows linearly with the size of the array.

Final Time Complexity

Time Complexity: O(n)

This means the time to delete grows in a straight line as the array gets bigger.

Common Mistake

[X] Wrong: "Deleting an element from the middle of an array is always fast and constant time."

[OK] Correct: Because after deletion, all elements after the deleted one must move, which takes time proportional to how many elements are after it.

Interview Connect

Understanding how array operations scale helps you explain trade-offs between arrays and other data structures like linked lists.

Self-Check

"What if we delete the first element instead of the middle? How would the time complexity change?"

Practice

1. What happens when you delete the middle element from an array of size 5?
int arr[5] = {10, 20, 30, 40, 50};
Delete the element at index 2 (middle). What is the new array?

easy

A. [10, 20, 40, 50]

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

C. [10, 20, 30, 50]

D. [20, 30, 40, 50]

Solution

1. Step 1: Identify the middle index and element

   The array has 5 elements, so the middle index is 2 (0-based). The element at index 2 is 30.

2. Step 2: Delete the middle element and shift remaining elements

   Remove 30, then shift elements after index 2 left by one: 40 moves to index 2, 50 moves to index 3.

3. Final Answer:

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

4. Quick Check:

   Middle element removed, array size reduced by 1 [OK]

Hint: Remove middle, shift right elements left by one [OK]

Common Mistakes:

• Not shifting elements after deletion
• Deleting wrong index
• Leaving array size unchanged

2. Which of the following C code snippets correctly deletes the middle element from an array arr of size n?

easy

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

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

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

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

Solution

1. Step 1: Identify the middle index and loop direction

   The middle index is n/2 (integer division). To delete, shift elements after middle left.

2. Step 2: Check loop correctness

   for (int i = n/2; i < n - 1; i++) arr[i] = arr[i + 1]; n--; shifts elements from middle to end left by one, then reduces size. This is correct.

3. Final Answer:

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

4. Quick Check:

   Shift elements after middle left [OK]

Hint: Shift elements from middle to end left by one [OK]

Common Mistakes:

• Shifting elements before middle
• Looping in wrong direction
• Not reducing array size

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

int arr[6] = {5, 10, 15, 20, 25, 30};
int n = 6;
int mid = n / 2;
for (int i = mid; i < n - 1; i++) {
    arr[i] = arr[i + 1];
}
n--;
for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
}

medium

A. 5 10 15 20 25 30

B. 5 10 15 20 30

C. 5 10 15 25 30

D. 5 10 20 25 30

Solution

1. Step 1: Calculate middle index and deletion

   n=6, mid=3. Element at index 3 is 20. It will be deleted.

2. Step 2: Shift elements after index 3 left by one

   arr[3] = arr[4] (25), arr[4] = arr[5] (30), n becomes 5.

3. Step 3: Print updated array

   Elements: 5, 10, 15, 25, 30

4. Final Answer:

   5 10 15 25 30 -> Option C

5. Quick Check:

   Deleted middle element, shifted right elements left [OK]

Hint: Delete middle, shift right elements left, print first n-1 elements [OK]

Common Mistakes:

• Printing original array size
• Not shifting elements correctly
• Deleting wrong index

4. Find the error in this code snippet that deletes the middle element from an array arr of size n:

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

medium

A. Middle index calculation is wrong, should be (n-1)/2

B. Loop shifts elements before middle, should shift after middle

C. Array size decrement should be before loop

D. No error, code is correct

Solution

1. Step 1: Analyze loop range and shifting direction

   The loop runs from 0 to mid-1, shifting elements before middle left, which is incorrect.

2. Step 2: Correct shifting after middle index

   To delete middle element, shift elements from middle index to end left by one, not before middle.

3. Final Answer:

   Loop shifts elements before middle, should shift after middle -> Option B

4. Quick Check:

   Shift elements after middle, not before [OK]

Hint: Shift elements after middle, not before [OK]

Common Mistakes:

• Shifting elements before middle
• Wrong loop boundaries
• Not reducing array size

5. Given an array arr of size n where n is even, write the steps to delete the middle two elements and shift the rest. What will be the new array after deleting middle elements from {1, 2, 3, 4, 5, 6}?

hard

A. [1, 2, 5, 6]

B. [1, 2, 3, 6]

C. [1, 2, 4, 5, 6]

D. [1, 3, 4, 5, 6]

Solution

1. Step 1: Identify middle two indices for even-sized array

   For n=6, middle two indices are 2 and 3 (0-based), elements 3 and 4.

2. Step 2: Delete these two elements and shift remaining elements left

   Shift elements from index 4 and 5 left by two positions: 5 moves to index 2, 6 moves to index 3. Reduce size by 2.

3. Step 3: New array after deletion

   Array becomes [1, 2, 5, 6]

4. Final Answer:

   [1, 2, 5, 6] -> Option A

5. Quick Check:

   Delete two middle elements, shift right elements left by two [OK]

Hint: Delete two middles, shift right elements left by two [OK]

Common Mistakes:

• Deleting only one middle element
• Shifting elements incorrectly
• Not reducing array size by two