26. Remove Duplicates from Sorted Array


Problem Description

The problem presents an integer array called nums that is sorted in non-decreasing order. The goal is to remove duplicates from nums in a way that each unique element appears only once while maintaining the relative order of elements. This task must be done in-place, which means that we should not allocate extra space for another array, and we have to modify the original array instead.

Once duplicates are removed, we are required to return the new length of the array, which represents the number of unique elements. The first part of the array up to this new length should contain all unique elements in their original order, and whatever follows after doesn't matter.

To adhere to the problem's constraints, the final arrangement of the array and the value of k are checked against the expected result using the provided custom judge implementation. In simple terms, after calling the solution function, the array nums should have its first k elements without duplicates and k should equal the expected number of unique elements.

Intuition

To arrive at the solution, we realize that since the array is already sorted, duplicates will be adjacent to each other. Hence, we can simply iterate through the array and compare each element with the previous one (except for the first element) to identify duplicates.

Our intuition should tell us that we need two pointers here: one for iterating over the array (x in this case) and another to keep track of the location in nums where the next unique element should be placed (k).

Starting with k at 0, we move through the array with x and when x is not equal to nums[k - 1] (which would mean x is not a duplicate), we place x at nums[k] and increment k. This works because when x is a duplicate of nums[k - 1], we simply skip it by not incrementing k, hence overwriting the duplicates in subsequent steps.

The process continues to the end of the array, ensuring that all unique elements are moved to the front of the array, and k represents the number of unique elements. By the end of the iteration, we return k as the result.

Learn more about Two Pointers patterns.

Solution Approach

The solution to this problem uses a technique commonly known as the two-pointer approach. This approach is often applied in array manipulation problems, especially when we need to modify the array in-place to satisfy certain constraints.

Here's how the two-pointer technique is applied step by step:

Step 1: Initialize Pointer k

A pointer k is initialized to 0. This pointer is used to track the position where the next unique element should be placed in the array.

Step 2: Iterate Through the Array

We iterate over each element x in the array nums. During iteration, k is used as a slow-runner pointer, while the loop index (implicitly represented by the iteration over x) acts as a fast-runner pointer.

Step 3: Identify Unique Elements

We only want to act when we come across a unique element. A unique element in this sorted array is identified by checking if it is different than the element at the position just before the current k. This is represented by the condition x != nums[k - 1].

Step 4: Place Unique Elements and Increment Pointer k

When a unique element is found, we copy it to nums[k] and then increment k. This effectively shifts the unique elements to the front of the array and steps over any duplicates.

The first element is a special case because there is no nums[k - 1] when k is 0, so it's always considered unique, and we start k at 0 by default.

Step 5: Handle Duplicates

When a duplicate element (which is not unique) is encountered, the body of the if condition does not execute, which means that k is not incremented. This implies that the duplicate value will be overwritten in the next iteration when a new unique element is encountered.

Step 6: Return the Count of Unique Elements

After the iteration is completed, k holds the total count of unique elements, as it was incremented only when encountering a unique element. We return k at the end.

Here is how the implementation looks in Python:

1class Solution:
2    def removeDuplicates(self, nums: List[int]) -> int:
3        k = 0
4        for x in nums:
5            if k == 0 or x != nums[k - 1]:
6                nums[k] = x
7                k += 1
8        return k

In this code, the if k == 0 check allows us to handle the first element correctly, and the subsequent x != nums[k - 1] checks help in identifying if the current element is different from the element that was last identified as unique.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Example Walkthrough

Let's assume we have the following sorted integer array nums:

1nums = [1, 1, 2, 2, 3]

Our goal is to remove duplicates using the algorithm described.

Initial Setup

We initialize k to 0. At this point, the array is unchanged.

Iteration 1

Element at index 0 is 1. Since k is 0, the first element is considered unique by default. We assign nums[k] to 1 and increment k to 1.

Updated array state:

1nums = [1, 1, 2, 2, 3]
2k = 1

Iteration 2

Element at index 1 is also 1. This is a duplicate of nums[k - 1]. We do not increment k.

Updated array state (no changes, duplicate ignored):

1nums = [1, 1, 2, 2, 3]
2k = 1

Iteration 3

Element at index 2 is 2. Now, nums[k - 1] is 1, so 2 is unique. We assign nums[k] to 2 and increment k to 2.

Updated array state:

1nums = [1, 2, 2, 2, 3]
2k = 2

Iteration 4

Element at index 3 is 2. This is a duplicate of nums[k - 1]. Again, k is not incremented.

Updated array state (no changes, duplicate ignored):

1nums = [1, 2, 2, 2, 3]
2k = 2

Iteration 5

Element at index 4 is 3. Now, nums[k - 1] is 2, so 3 is unique. We assign nums[k] to 3 and increment k to 3.

Updated array state:

1nums = [1, 2, 3, 2, 3]
2k = 3

Conclusion

We've finished iterating over nums. The first k (3) elements [1, 2, 3] are the unique numbers from the original array. The rest of the array doesn't matter for this problem.

We return k, which is 3, indicating the number of unique elements in the modified array.

The final state of nums is:

1nums = [1, 2, 3, 2, 3]

And the returned value is 3.

Solution Implementation

1class Solution:
2    def removeDuplicates(self, nums: List[int]) -> int:
3        # Initialize the array position marker k to 0.
4        # This will keep track of the position in the array
5        # where the next unique element should be placed.
6        k = 0
7      
8        # Loop through each number in the nums array.
9        for x in nums:
10            # Check if k is 0, which means we're at the start of the array
11            # or if the current number is not equal to the last unique number we've seen.
12            # The condition k == 0 is true for the first element,
13            # so we store it as the first unique element.
14            if k == 0 or x != nums[k - 1]:
15                # Place the current unique element at the k-th position in the array.
16                nums[k] = x
17                # Increment k to indicate that the next unique element should be placed in the next position.
18                k += 1
19      
20        # Return the length of the array that contains all unique elements,
21        # which is also the new length of the array without duplicates.
22        return k
23
1class Solution {
2    // Method to remove duplicates from sorted array
3    // and return the length of the array after duplicates have been removed.
4    public int removeDuplicates(int[] nums) {
5        // Initialize the count for unique elements
6        int uniqueCount = 0;
7      
8        // Iterate over each element in the array
9        for (int currentNum : nums) {
10            // If it's the first element or is not equal to the previous element
11            // (which means it's not a duplicate)
12            if (uniqueCount == 0 || currentNum != nums[uniqueCount - 1]) {
13                // Assign the current number to the next unique position in the array
14                nums[uniqueCount++] = currentNum;
15            }
16        }
17      
18        // Return the count of unique elements, which is also the new length of the array
19        return uniqueCount;
20    }
21}
22
1#include <vector> // Required to use the std::vector container
2
3// Solution class encapsulates the method to remove duplicates from an array.
4class Solution {
5public:
6    // Method to remove duplicates from a sorted vector in-place.
7    // @param nums is a reference to a vector of integers.
8    // @return The new length of the vector after duplicates have been removed.
9    int removeDuplicates(std::vector<int>& nums) {
10        // The std::unique function returns an iterator to the element that follows the last element
11        // not removed. The range between this iterator and the end of the vector contains all the 
12        // elements that need to be removed.
13        auto newEnd = std::unique(nums.begin(), nums.end());
14
15        // Erase the non-unique elements from the vector using the erase function.
16        // This mutates the vector and adjusts its size accordingly.
17        nums.erase(newEnd, nums.end());
18
19        // Return the new size of the vector after removing duplicates.
20        return nums.size();
21    }
22};
23
1/**
2 * Removes all duplicates from a sorted array of numbers.
3 * Duplicates are removed in-place and the function returns
4 * the new length of the array after duplicates have been removed.
5 *
6 * @param {number[]} nums - A sorted array of numbers from which to remove duplicates.
7 * @return {number} The new length of the array after duplicate removal.
8 */
9function removeDuplicates(nums: number[]): number {
10    // Initialize the index for the next unique element.
11    let nextUniqueIndex: number = 0;
12
13    // Iterate through the array of numbers.
14    for (const currentElement of nums) {
15        // If we're at the start of the array or the current element is not 
16        // the same as the last unique element, we treat it as unique.
17        if (nextUniqueIndex === 0 || currentElement !== nums[nextUniqueIndex - 1]) {
18            // Store the current element at the next unique position.
19            nums[nextUniqueIndex] = currentElement;
20            // Increment the index for the next unique element.
21            nextUniqueIndex++;
22        }
23        // If the current element is the same as the last unique element,
24        // the loop continues without doing anything, effectively skipping duplicates.
25    }
26
27    // Return the new length of the array after all duplicates have been removed.
28    // This length is equivalent to the next unique element's index.
29    return nextUniqueIndex;
30}
31

Time and Space Complexity

Time Complexity:

The given algorithm iterates through each element of the list exactly once. During each iteration, the algorithm performs a constant number of operations: a comparison, an assignment (when necessary), and an increment of the k counter. The time complexity is therefore linear relative to the length of the input list nums. If n represents the number of elements in nums, the time complexity can be expressed as O(n).

Space Complexity:

The algorithm modifies the list nums in place and does not require any additional space that grows with the size of the input, except for the counter variable k. Therefore, the auxiliary space requirement is constant, and the space complexity is O(1).

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


Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄