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 understand how the time needed to remove duplicates from a sorted array grows as the array gets bigger.

Specifically, how does the process of scanning and updating the array scale with its size?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int removeDuplicates(std::vector<int>& nums) {
    int i = 0;
    for (int j = 1; j < nums.size(); 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

• Primary operation: The for-loop that scans the array once from start to end.
• How many times: It runs exactly once for each element after the first, so about n-1 times for an array of size n.

How Execution Grows With Input

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

Input Size (n)	Approx. Operations
10	About 9 comparisons and possible assignments
100	About 99 comparisons and possible assignments
1000	About 999 comparisons and possible assignments

Pattern observation: The operations increase linearly as the input size increases.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Since we check pairs, the time complexity is O(n²)."

[OK] Correct: We only scan the array once with two pointers moving forward, so each element is visited once, not repeatedly.

Interview Connect

Understanding this linear time approach shows you can efficiently handle arrays without extra space, a common skill interviewers look for.

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 the two-pointer technique in removing duplicates from a sorted array?

easy

A. To track unique elements and overwrite duplicates in-place

B. To sort the array again after removing duplicates

C. To create a new array with duplicates removed

D. To count the total number of duplicates only

Solution

1. Step 1: Understand the two-pointer roles

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

2. Step 2: Overwrite duplicates in-place

   When a new unique element is found, it is placed at the tracked position, replacing duplicates.

3. Final Answer:

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

4. Quick Check:

   Two-pointer technique = overwrite duplicates [OK]

Hint: Two pointers: one scans, one writes unique values [OK]

Common Mistakes:

• Thinking it creates a new array instead of modifying in-place
• Assuming it sorts the array again
• Confusing counting duplicates with removing them

2. Which of the following is the correct syntax to initialize the two pointers for removing duplicates from a sorted array nums in C++?

easy

A. int i = 0, j = 1;

B. int i = 1, j = 0;

C. int i = 0, j = 0;

D. int i = 1, j = 1;

Solution

1. Step 1: Identify pointer roles

   Pointer i tracks the last unique element index, starting at 0; j scans from 1.

2. Step 2: Initialize pointers accordingly

   Set i = 0 and j = 1 to start comparing from the second element.

3. Final Answer:

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

4. Quick Check:

   i=0, j=1 start positions [OK]

Hint: Start i at 0, j at 1 to compare neighbors [OK]

Common Mistakes:

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

3. What will be the output length after removing duplicates using the two-pointer method on the sorted array nums = {1, 1, 2, 3, 3, 4}?

medium

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Identify unique elements in order

   Unique elements are 1, 2, 3, 4.

2. Step 2: Count unique elements

   There are 4 unique elements, so the length after removal is 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Unique count = 4 [OK]

Hint: Count unique numbers in sorted array [OK]

Common Mistakes:

• Counting duplicates as unique
• Confusing length with original array size
• Off-by-one errors in counting

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

int removeDuplicates(vector<int>& nums) {
    int i = 0, j = 1;
    while (j < nums.size()) {
        if (nums[i] != nums[j]) {
            i++;
            nums[i] = nums[j];
        }
        j++;
    }
    return i;
}

medium

A. The loop should use for instead of while

B. Pointers i and j should start at 1 and 0 respectively

C. The condition should be nums[i] == nums[j] instead of !=

D. Return value should be i + 1, not i

Solution

1. Step 1: Understand pointer i meaning

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

2. Step 2: Check return statement

   Returning i alone gives index, not count; must return i + 1 for length.

3. Final Answer:

   Return value should be i + 1, not i -> Option D

4. Quick Check:

   Length = last index + 1 [OK]

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

Common Mistakes:

• Returning i instead of i + 1
• Swapping pointer initializations
• Using wrong comparison operator

5. Given a sorted array nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4}, what will be the state of the array after applying the two-pointer method to remove duplicates, and what is the new length?

hard

A. Array: {0, 1, 1, 2, 3, 4, _, _, _, _}, Length: 4

B. Array: {0, 0, 1, 1, 2, 2, 3, 3, 4, 4}, Length: 6

C. Array: {0, 1, 2, 3, 4, _, _, _, _, _}, Length: 5

D. Array: {0, 1, 2, 3, 4, 5, _, _, _, _}, Length: 6

Solution

1. Step 1: Identify unique elements in order

   Unique elements are 0, 1, 2, 3, 4.

2. Step 2: Overwrite duplicates in-place

   Using two pointers, these unique elements overwrite the start of the array.

3. Step 3: Determine new length

   There are 5 unique elements, so length is 5.

4. Final Answer:

   Array: {0, 1, 2, 3, 4, _, _, _, _, _}, Length: 5 -> Option C

5. Quick Check:

   Unique elements = 5, array start updated [OK]

Hint: Unique elements overwrite start, length = count unique [OK]

Common Mistakes:

• Not overwriting duplicates correctly
• Miscounting unique elements
• Assuming array length stays same