Remove Duplicates from Sorted Array Two Pointer in DSA C# - Time & Space Complexity

Time Complexity: Remove Duplicates from Sorted Array Two Pointer

O(n)

Understanding Time Complexity

We want to know how the time to remove duplicates from a sorted array grows as the array gets bigger.

How many steps does the algorithm take when the input size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public int RemoveDuplicates(int[] nums) {
    int i = 0;
    for (int j = 1; j < nums.Length; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}
    

This code removes duplicates from a sorted array by using two pointers to overwrite duplicates in place.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that moves pointer j from start to end of the array.
• How many times: Exactly once for each element after the first, so n - 1 times where n is the array length.

How Execution Grows With Input

As the array size grows, the loop runs once for each element, so the steps increase directly with input size.

Input Size (n)	Approx. Operations
10	9
100	99
1000	999

Pattern observation: The number of operations grows linearly as the input size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to remove duplicates grows in direct proportion to the size of the input array.

Common Mistake

[X] Wrong: "Because there are two pointers, the time complexity is O(n²)."

[OK] Correct: The two pointers move forward independently but only once through the array, so the total steps are still proportional to n, not n squared.

Interview Connect

Understanding this linear time approach shows you can efficiently process arrays without extra space, a skill often needed in real coding tasks.

Self-Check

"What if the array was not sorted? How would the time complexity change if we still tried to remove duplicates in place?"

Practice

1. What is the main purpose of using two pointers in the Remove Duplicates from Sorted Array problem?

easy

A. To create a new array with unique elements

B. To sort the array before removing duplicates

C. To efficiently track unique elements and overwrite duplicates in-place

D. To count the total number of duplicates in the array

Solution

1. Step 1: Understand the two-pointer approach

   One pointer tracks the position to place the next unique element, the other scans the array.

2. Step 2: Purpose of pointers in-place

   This method avoids extra space by overwriting duplicates directly in the original array.

3. Final Answer:

   To efficiently track unique elements and overwrite duplicates in-place -> Option C

4. Quick Check:

   Two pointers help remove duplicates in-place [OK]

Hint: Two pointers track and overwrite duplicates without extra space [OK]

Common Mistakes:

• Thinking two pointers sort the array
• Assuming a new array is created
• Confusing counting duplicates with removing them

2. Which of the following is the correct C# syntax to initialize the two pointers i and j for the problem?

easy

A. int i = 1; int j = 1;

B. int i = 1, j = 0;

C. int i = 0; int j = 0;

D. int i = 0, j = 1;

Solution

1. Step 1: Identify pointer roles

   Pointer i starts at index 0 to track unique elements, j starts at 1 to scan ahead.

2. Step 2: Check initialization correctness

   Initializing i = 0 and j = 1 matches the logic of comparing current and next elements.

3. Final Answer:

   int i = 0, j = 1; -> Option D

4. Quick Check:

   Start i at 0 and j at 1 [OK]

Hint: Start i at 0 and j at 1 to compare adjacent elements [OK]

Common Mistakes:

• Starting both pointers at 0
• Swapping i and j initialization
• Starting both pointers at 1

3. What will be the output array and new length after running the two-pointer method on the sorted array [1, 1, 2, 3, 3]?

medium

A. [1, 2, 3, 3], length = 4

B. [1, 2, 3], length = 3

C. [1, 1, 2, 3, 3], length = 5

D. [1, 2, 2, 3], length = 4

Solution

1. Step 1: Trace the two-pointer process

   Start with i=0, j=1. Compare elements: skip duplicates, overwrite unique elements at i+1.

2. Step 2: Final array and length

   Unique elements are 1, 2, 3 placed at start. Length is 3.

3. Final Answer:

   [1, 2, 3], length = 3 -> Option B

4. Quick Check:

   Unique elements count = 3 [OK]

Hint: Overwrite duplicates, count unique elements for length [OK]

Common Mistakes:

• Not updating length after removal
• Leaving duplicates in output
• Misplacing unique elements

4. Identify the error in the following C# code snippet for removing duplicates from a sorted array:

int RemoveDuplicates(int[] nums) {
    int i = 0, j = 1;
    while (j < nums.Length) {
        if (nums[i] != nums[j]) {
            i++;
            nums[i] = nums[j];
        }
        j++;
    }
    return i;
}

medium

A. The function should return i + 1 instead of i

B. Pointers i and j should both start at 1

C. The while loop condition should be j <= nums.Length

D. The array should be sorted inside the function

Solution

1. Step 1: Understand pointer meaning

   Pointer i tracks last unique element index, so length is i + 1.

2. Step 2: Check return value

   Returning i alone misses counting the first element, so return i + 1.

3. Final Answer:

   The function should return i + 1 instead of i -> Option A

4. Quick Check:

   Return length as i + 1 [OK]

Hint: Return i + 1 as length, not just i [OK]

Common Mistakes:

• Returning i instead of i + 1
• Incorrect loop boundary causing out-of-range
• Sorting array inside function unnecessarily

5. Given a sorted array nums = [0,0,1,1,1,2,2,3,3,4], what will be the array state and returned length after applying the two-pointer duplicate removal method?

hard

A. [0, 1, 2, 3, 4], length = 5

B. [0, 0, 1, 2, 3, 4], length = 6

C. [0, 1, 1, 2, 3, 4], length = 6

D. [0, 1, 2, 3, 3, 4], length = 6

Solution

1. Step 1: Apply two-pointer method step-by-step

   Start with i=0, j=1. Move j forward, overwrite duplicates by placing unique elements at i+1.

2. Step 2: Final array and length

   Unique elements are 0,1,2,3,4 placed at start. Length is 5.

3. Final Answer:

   [0, 1, 2, 3, 4], length = 5 -> Option A

4. Quick Check:

   Unique count = 5 [OK]

Hint: Overwrite duplicates, count unique elements for final length [OK]

Common Mistakes:

• Leaving duplicates in the array
• Returning wrong length
• Misplacing unique elements during overwrite