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

Time Complexity: Remove Duplicates from Sorted Array Two Pointer

O(n)

Understanding Time Complexity

We want to know how fast the two-pointer method removes duplicates from a sorted array.

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

    def remove_duplicates(nums):
        if not nums:
            return 0
        i = 0
        for j in range(1, len(nums)):
            if nums[j] != nums[i]:
                i += 1
                nums[i] = nums[j]
        return i + 1
    

This code removes duplicates in-place from a sorted array using two pointers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: One loop that goes through the array once.
• How many times: The loop runs once for each element after the first.

How Execution Grows With Input

As the array size grows, the loop runs more times, directly proportional to the size.

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

Pattern observation: The number of operations grows linearly with input size.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Because there are two pointers, the time is doubled or squared."

[OK] Correct: Both pointers move forward through the array only once, so the total work is still proportional to the array size, not squared.

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?"