Problem Description

You are given an integer array nums that is sorted in non-decreasing order. Your task is to remove duplicates from this array in-place so that each unique element appears only once, while maintaining the relative order of elements. After removing duplicates, you need to return the count of unique elements.

The key requirements are:

• The modification must be done in-place (without using extra array space)
• After your function runs, the first k elements of nums should contain all unique elements in their original order, where k is the number of unique elements
• The elements beyond the first k positions don't matter
• Return the value k

For example:

• If nums = [1,1,2], after calling your function:

  • The first 2 elements of nums should be [1,2]
  • Return 2 (the count of unique elements)

• If nums = [0,0,1,1,1,2,2,3,3,4], after calling your function:

  • The first 5 elements of nums should be [0,1,2,3,4]
  • Return 5 (the count of unique elements)

The judge will verify your solution by checking that:

1. The returned value k matches the expected number of unique elements
2. The first k elements in the modified array match the expected unique elements in order

Intuition

Since the array is already sorted, duplicate elements will always be adjacent to each other. This is the key insight that makes the problem simpler - we don't need to look through the entire array to check for duplicates, we only need to compare consecutive elements.

The challenge is doing this in-place. We need to somehow "compact" the array by keeping only unique elements at the beginning. Think of it like having two pointers:

• One pointer reads through all elements in the array
• Another pointer marks where to place the next unique element

We can use a variable k to track the position where the next unique element should be placed. As we iterate through the array:

• If we're at the very first element (k == 0), it's definitely unique, so we keep it
• For any other element x, we compare it with the element at position k-1 (the last unique element we've kept)
• If x is different from nums[k-1], then x is a new unique element - we place it at position k and increment k
• If x equals nums[k-1], it's a duplicate of what we already have, so we skip it

This way, we're essentially building a new array of unique elements within the original array, overwriting from the beginning. The beauty of this approach is that we're always comparing with the last unique element we've found (nums[k-1]), not the immediately previous element in the original array. This ensures we correctly identify all unique values even when there are multiple consecutive duplicates.

By the end of the traversal, k tells us exactly how many unique elements we found, and these elements are neatly arranged in the first k positions of the array.

Learn more about Two Pointers patterns.

Solution Approach

The implementation uses a single-pass algorithm with a two-pointer technique. Here's how the solution works step by step:

Algorithm Setup:

• Initialize a variable k = 0 to track the position where the next unique element should be placed
• k also represents the current length of the processed (unique elements) array

Main Loop: Iterate through each element x in the array nums:

1. Check if element should be kept:

   • If k == 0 (empty processed array), the current element is the first one and must be kept
   • OR if x != nums[k-1] (current element is different from the last kept unique element)

2. Place the unique element:

   • When either condition above is true, place x at position nums[k]
   • Increment k by 1 to move to the next available position

3. Skip duplicates:

   • If x == nums[k-1], the element is a duplicate, so we simply continue to the next iteration without modifying k

Example walkthrough with nums = [1,1,2]:

• Initially: k = 0
• First iteration (x = 1): k == 0 is true, so nums[0] = 1, k = 1
• Second iteration (x = 1): k != 0 and 1 == nums[0], skip this duplicate
• Third iteration (x = 2): k != 0 and 2 != nums[0], so nums[1] = 2, k = 2
• Result: nums = [1,2,...], return k = 2

Time and Space Complexity:

• Time Complexity: O(n) where n is the length of the array, as we make a single pass through all elements
• Space Complexity: O(1) as we only use a constant amount of extra space (the variable k)

The elegance of this solution lies in using the array itself as the storage for the result, overwriting from the beginning while maintaining the relative order of unique elements.

Example Walkthrough

Let's walk through the solution with nums = [0,0,1,1,1,2,2,3,3,4]:

Initial Setup:

• k = 0 (position for next unique element)
• Array: [0,0,1,1,1,2,2,3,3,4]

Iteration 1 (x = 0, index 0):

• Check: k == 0? Yes, this is our first element
• Action: Place 0 at position k → nums[0] = 0
• Update: k = 1
• Array state: [0,0,1,1,1,2,2,3,3,4] (unchanged visually, but k moved)

Iteration 2 (x = 0, index 1):

• Check: k == 0? No. Is 0 != nums[0]? No (0 == 0)
• Action: Skip this duplicate
• Array state: [0,0,1,1,1,2,2,3,3,4], k remains 1

Iteration 3 (x = 1, index 2):

• Check: k == 0? No. Is 1 != nums[0]? Yes (1 ≠ 0)
• Action: Place 1 at position k → nums[1] = 1
• Update: k = 2
• Array state: [0,1,1,1,1,2,2,3,3,4]

Iterations 4-5 (x = 1, indices 3-4):

• Both are duplicates of nums[1] = 1, so skip both
• k remains 2

Iteration 6 (x = 2, index 5):

• Check: Is 2 != nums[1]? Yes (2 ≠ 1)
• Action: Place 2 at position k → nums[2] = 2
• Update: k = 3
• Array state: [0,1,2,1,1,2,2,3,3,4]

Iteration 7 (x = 2, index 6):

• Duplicate of nums[2] = 2, skip
• k remains 3

Iteration 8 (x = 3, index 7):

• Check: Is 3 != nums[2]? Yes (3 ≠ 2)
• Action: Place 3 at position k → nums[3] = 3
• Update: k = 4
• Array state: [0,1,2,3,1,2,2,3,3,4]

Iteration 9 (x = 3, index 8):

• Duplicate of nums[3] = 3, skip
• k remains 4

Iteration 10 (x = 4, index 9):

• Check: Is 4 != nums[3]? Yes (4 ≠ 3)
• Action: Place 4 at position k → nums[4] = 4
• Update: k = 5
• Final array state: [0,1,2,3,4,2,2,3,3,4]

Result:

• Return k = 5
• First 5 elements are [0,1,2,3,4] - all unique values in order
• Elements after position 4 don't matter

The key insight: we always compare with nums[k-1] (the last unique element we kept), not with the previous element in the iteration. This ensures we correctly identify unique values even when there are multiple consecutive duplicates.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

• The algorithm iterates through the input array nums exactly once using a single for loop
• Each iteration performs constant time operations: comparison (x != nums[k - 1]), assignment (nums[k] = x), and increment (k += 1)
• Since we visit each of the n elements exactly once with O(1) work per element, the total time complexity is O(n)

Space Complexity: O(1)

• The algorithm modifies the input array in-place without using any additional data structures
• Only a constant amount of extra space is used for the variable k (counter) and the loop variable x
• The space usage does not scale with the input size, resulting in O(1) auxiliary space complexity

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Comparing with the Wrong Element

A frequent mistake is comparing the current element with nums[write_index] instead of nums[write_index - 1]:

Incorrect Code:

def removeDuplicates(self, nums: List[int]) -> int:
    write_index = 0
    for current_num in nums:
        # WRONG: Comparing with nums[write_index] instead of nums[write_index - 1]
        if write_index == 0 or current_num != nums[write_index]:
            nums[write_index] = current_num
            write_index += 1
    return write_index

Why this fails: nums[write_index] hasn't been set yet or contains an old value that will be overwritten. You need to compare with the last placed unique element at nums[write_index - 1].

2. Using a Separate Read Pointer Unnecessarily

Some attempt to use two explicit pointers, making the code more complex:

Overly Complex Code:

def removeDuplicates(self, nums: List[int]) -> int:
    if not nums:
        return 0
  
    read_ptr = 1  # Unnecessary separate read pointer
    write_ptr = 1
  
    while read_ptr < len(nums):
        if nums[read_ptr] != nums[write_ptr - 1]:
            nums[write_ptr] = nums[read_ptr]
            write_ptr += 1
        read_ptr += 1
  
    return write_ptr

Better approach: Use the for loop's implicit iteration as the read pointer, keeping only the write pointer explicit.

3. Forgetting Edge Cases

Incorrect handling of empty array:

def removeDuplicates(self, nums: List[int]) -> int:
    write_index = 1  # WRONG: Assumes at least one element
  
    for i in range(1, len(nums)):  # Skips first element
        if nums[i] != nums[write_index - 1]:
            nums[write_index] = nums[i]
            write_index += 1
  
    return write_index

Why this fails: This crashes on empty arrays and unnecessarily complicates the logic by starting from index 1.

4. Modifying the Array While Iterating Incorrectly

Attempting to delete elements:

def removeDuplicates(self, nums: List[int]) -> int:
    i = 1
    while i < len(nums):
        if nums[i] == nums[i-1]:
            nums.pop(i)  # WRONG: Not in-place as required
        else:
            i += 1
    return len(nums)

Why this fails: Using pop() or del operations has O(n) time complexity for each removal, making the overall complexity O(n²). Also, this approach doesn't meet the "in-place with O(1) space" requirement as pop() operations can trigger array resizing.

5. Off-by-One Errors in Index Checking

Incorrect boundary check:

def removeDuplicates(self, nums: List[int]) -> int:
    write_index = 0
  
    for current_num in nums:
        # WRONG: Should check write_index == 0, not write_index <= 0
        if write_index < 1 or current_num != nums[write_index - 1]:
            nums[write_index] = current_num
            write_index += 1
  
    return write_index

Why this matters: While write_index < 1 works functionally, it's less clear in intent. Using write_index == 0 explicitly shows you're checking for the first element case.

Correct Solution Pattern:

• Always compare with nums[write_index - 1] (the last placed unique element)
• Handle the first element with write_index == 0 check
• Use a single write pointer with the for loop as implicit read pointer
• Never use operations that modify array size (pop, del, insert)