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

Time Complexity: Array Insertion at Middle Index

O(n)

Understanding Time Complexity

We want to understand how long it takes to insert an element in the middle of an array.

How does the time needed change as the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int[] InsertAtMiddle(int[] arr, int value) {
    int n = arr.Length;
    int mid = n / 2;
    int[] newArr = new int[n + 1];
    for (int i = 0; i < mid; i++) {
        newArr[i] = arr[i];
    }
    newArr[mid] = value;
    for (int i = mid; i < n; i++) {
        newArr[i + 1] = arr[i];
    }
    return newArr;
}
    

This code inserts a new value in the middle of an array by creating a new array and shifting elements.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two for-loops copying elements before and after the middle index.
• How many times: Each loop runs about n/2 times, so together they run roughly n times.

How Execution Grows With Input

As the array size grows, the number of copy operations grows roughly the same way.

Input Size (n)	Approx. Operations
10	About 10 copy steps
100	About 100 copy steps
1000	About 1000 copy steps

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

Final Time Complexity

Time Complexity: O(n)

This means the time to insert grows in a straight line with the array size.

Common Mistake

[X] Wrong: "Inserting in the middle is as fast as adding at the end."

[OK] Correct: Inserting in the middle requires shifting many elements, unlike adding at the end which can be faster.

Interview Connect

Understanding this helps you explain why arrays are not always best for insertions, a key skill in coding interviews.

Self-Check

"What if we used a linked list instead of an array? How would the time complexity change?"

Practice

1. What happens when you insert an element at the middle index of an array in C#?

easy

A. The array size decreases by one.

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

C. The new element replaces the element at the middle index without shifting.

D. The array elements remain unchanged.

Solution

1. Step 1: Understand array insertion behavior

   When inserting at the middle, elements from that index onward must move right to avoid overwriting.

2. Step 2: Effect on array size and elements

   The array size increases by one, and elements after the middle index shift right to make space.

3. Final Answer:

   Elements after the middle index shift right to make space for the new element. -> Option B

4. Quick Check:

   Insertion shifts elements right = A [OK]

Hint: Insertion shifts elements right from middle index [OK]

Common Mistakes:

• Thinking the array size decreases
• Replacing element without shifting
• Assuming no change in elements

2. Which of the following is the correct syntax to insert an element at the middle index of an array in C# (assuming you use a List<int> named 'numbers')?

easy

A. numbers.AddAtMiddle(10);

B. numbers.Add(10, numbers.Count / 2);

C. numbers.InsertAtMiddle(10);

D. numbers.Insert(numbers.Count / 2, 10);

Solution

1. Step 1: Identify List insertion method

   List<T> in C# uses Insert(index, value) to insert at any position.

2. Step 2: Calculate middle index and insert

   Middle index is numbers.Count / 2; so Insert(numbers.Count / 2, 10) inserts 10 at middle.

3. Final Answer:

   numbers.Insert(numbers.Count / 2, 10); -> Option D

4. Quick Check:

   Insert(index, value) syntax = B [OK]

Hint: Use Insert(index, value) with middle index [OK]

Common Mistakes:

• Using non-existent methods like AddAtMiddle
• Confusing Add and Insert parameters
• Wrong method names

3. What will be the output of the following C# code?

List<int> nums = new List<int> {1, 2, 3, 4, 5};
nums.Insert(nums.Count / 2, 99);
Console.WriteLine(string.Join(", ", nums));

medium

A. 1, 2, 3, 99, 4, 5

B. 1, 2, 3, 4, 5, 99

C. 1, 2, 99, 3, 4, 5

D. 99, 1, 2, 3, 4, 5

Solution

1. Step 1: Calculate middle index

   nums.Count is 5, so middle index = 5 / 2 = 2.

2. Step 2: Insert 99 at index 2

   Original list: [1, 2, 3, 4, 5]. After insertion: [1, 2, 99, 3, 4, 5].

3. Final Answer:

   1, 2, 99, 3, 4, 5 -> Option C

4. Quick Check:

   Insert at index 2 shifts elements right = D [OK]

Hint: Middle index = Count/2; insert shifts elements right [OK]

Common Mistakes:

• Inserting at wrong index
• Appending instead of inserting
• Miscounting middle index

4. The following code tries to insert an element at the middle index of an array but does not insert properly. What is the issue and how to fix it?

int[] arr = {1, 2, 3, 4};
int middle = arr.Length / 2;
arr[middle] = 99;

medium

A. Error: Cannot insert in fixed-size array; use List<int> and Insert method.

B. No error; code works fine.

C. Error: Index out of range; middle index calculation is wrong.

D. Error: Assignment operator is invalid here.

Solution

1. Step 1: Understand array size and insertion

   Arrays in C# have fixed size; you cannot insert elements to increase size.

2. Step 2: Fix by using List<int> and Insert method

   Use List<int> which supports dynamic insertion with Insert(index, value).

3. Final Answer:

   Error: Cannot insert in fixed-size array; use List<int> and Insert method. -> Option A

4. Quick Check:

   Fixed-size arrays can't insert = A [OK]

Hint: Arrays fixed size; use List for insertion [OK]

Common Mistakes:

• Thinking assignment inserts element
• Misunderstanding array size limits
• Wrong index calculation assumption

5. You have an array of integers with an even length. You want to insert a new element exactly in the middle so that the array size increases by one and elements after the middle shift right. Which approach is best in C#?

hard

A. Use a List<int>, insert at middle index, then convert back to array if needed.

B. Directly assign the new element at middle index in the existing array.

C. Create a new array with size +1, copy elements before middle, insert new element, then copy remaining elements.

D. Use Array.Resize to increase size and then assign at middle index.

Solution

1. Step 1: Understand array limitations

   Arrays have fixed size; direct insertion is not possible without creating a new array.

2. Step 2: Use List for dynamic insertion

   List<int> allows insertion at any index easily; after insertion, convert back to array if needed.

3. Final Answer:

   Use a List<int>, insert at middle index, then convert back to array if needed. -> Option A

4. Quick Check:

   List supports insertion; arrays do not [OK]

Hint: Use List for easy insertion, then convert to array [OK]

Common Mistakes:

• Trying to assign directly in fixed array
• Using Array.Resize incorrectly
• Manually copying arrays without List