Easy

Remove Duplicates from Sorted Array

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Problem Statement

The problem is to remove the duplicates from an input integer array nums that is sorted in non-decreasing order, such that each unique element appears only once. The relative order of the elements in the array should be kept the same. The final result should be placed in the first part of the array nums with a length k, which represents the number of unique elements in the array after removing duplicates. The algorithm must not allocate extra space for another array and should modify the input array nums in-place with O(1) extra memory. The function should return k after placing the final result in the first k slots of nums.

Examples

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Clarifying Questions

Can I assume that the input array nums will always be sorted in non-decreasing order?
Is it okay to modify the order of the duplicate elements in the final result as long as each unique element appears only once?
Can I assume that the array nums is not null or empty?
Can I assume that the elements in the array nums are integers?
Can I use additional data structures such as hash tables or sets to solve this problem?

Solutions

There are several different approaches to solving this problem:

Two Pointers
Hash Set
Using built-in functions
Binary Search
Two Pointers with Swap

Approach 1: Two Pointers

Use two pointers to iterate through the array. One pointer will iterate through the array while the other pointer will keep track of the unique elements found so far. Duplicate elements will be skipped and unique elements will be copied to the unique elements pointer. This approach has a time complexity of O(n) and a space complexity of O(1).

Algorithm:

Initialize two pointers, i and j, to 0.
While j is less than the length of the array:
- If the value at index j is different from the value at index i, increment i and copy the value at index j to the new position at index i.
- Increment j.
Return i.

      
     
        public int RemoveDuplicates(int[] nums) {
            if (nums == null || nums.Length == 0) {
                return 0;
            }
            int i = 0; // Initialize pointer i to 0
            // Iterate through the array with pointer j
            for (int j = 0; j < nums.Length; j++) { 
                // Check if the current value is not a duplicate
                if (j == 0 || nums[j] != nums[j-1]) {
                    // Copy the current value to the new position at index i
                    nums[i] = nums[j]; 
                    i++; // Increment pointer i
                }
            }
            return i; // Return the number of unique elements
        }

      
     
        def removeDuplicates(nums: List[int]) -> int:
            i = 0 # Initialize pointer i to 0
            for j in range(len(nums)): # Iterate through the array with pointer j
                if j == 0 or nums[j] != nums[j-1]: # Check if the current value is not a duplicate
                    nums[i] = nums[j] # Copy the current value to the new position at index i
                    i += 1 # Increment pointer i
            return i # Return the number of unique elements

      
     
        public int removeDuplicates(int[] nums) {
            int i = 0; // Initialize pointer i to 0
            for (int j = 0; j < nums.length; j++) { // Iterate through the array with pointer j
                if (j == 0 || nums[j] != nums[j-1]) { // Check if the current value is not a duplicate
                    nums[i] = nums[j]; // Copy the current value to the new position at index i
                    i++; // Increment pointer i
                }
            }
            return i; // Return the number of unique elements
        }

      
   
    int removeDuplicates(vector<int>& nums) {
        int i = 0; // Initialize pointer i to 0
        for (int j = 0; j < nums.size(); j++) { // Iterate through the array with pointer j
            if (j == 0 || nums[j] != nums[j-1]) { // Check if the current value is not a duplicate
                nums[i] = nums[j]; // Copy the current value to the new position at index i
                i++; // Increment pointer i
            }
        }
        return i; // Return the number of unique elements
    }

Time complexity: O(n), where n is the length of the input array. This is because we traverse the input array exactly once.
Space complexity: O(1), because we modify the input array in-place without using any extra memory.

Approach 2: Hash Set

Use a hash set to keep track of unique elements while iterating through the array. Duplicate elements will be skipped and unique elements will be added to the hash set. This approach has a time complexity of O(n) and a space complexity of O(n).

Algorithm:

Initialize a hash set to keep track of unique elements.
Initialize a variable k to 0.
Iterate through the array:
- If the value at index i is not in the hash set, add it to the hash set and copy it to the new position at index k.
- Increment k.
Return k.

      
        public int RemoveDuplicates(int[] nums) {
            HashSet<int> set = new HashSet<int>(); // Initialize a hash set to keep track of unique elements
            int k = 0; // Initialize a variable k to 0
            for (int i = 0; i < nums.Length; i++) { // Iterate through the array
                if (set.Add(nums[i])) { // Check if the value is not in the hash set
                    nums[k] = nums[i]; // Copy the current value to the new position at index k
                    k++; // Increment k
                }
            }
            return k; // Return the number of unique elements
        }

      
     
        def removeDuplicates(nums: List[int]) -> int:
            unique = set() # Initialize a set to keep track of unique elements
            k = 0 # Initialize a variable k to 0
            for i in range(len(nums)): # Iterate through the array
                if nums[i] not in unique: # Check if the value is not in the set
                    unique.add(nums[i]) # Add the value to the set
                    nums[k] = nums[i] # Copy the current value to the new position at index k
                    k += 1 # Increment k
            return k # Return the number of unique elements

      
        public int removeDuplicates(int[] nums) {
            HashSet<Integer> set = new HashSet<>(); // Initialize a hash set to keep track of unique elements
            int k = 0; // Initialize a variable k to 0
            for (int i = 0; i < nums.length; i++) { // Iterate through the array
                if (set.add(nums[i])) { // Check if the value is not in the hash set
                    nums[k] = nums[i]; // Copy the current value to the new position at index k
                    k++; // Increment k
                }
            }
            return k; // Return the number of unique elements
        }

      

int removeDuplicates(vector<int>& nums) {
    unordered_set<int> set; // Initialize a hash set to keep track of unique elements
    int k = 0; // Initialize a variable k to 0
    for (int i = 0; i < nums.size(); i++) { // Iterate through the array
        if (set.insert(nums[i]).second) { // Check if the value is not in the hash set
            nums[k] = nums[i]; // Copy the current value to the new position at index k
            k++; // Increment k
        }
    }
    return k; // Return the number of unique elements
}

Note: In the C++ implementation, we use an unordered_set instead of a set to achieve constant time average insertions and lookups. The .second attribute of the insert function returns a boolean indicating whether the insertion was successful or not.

Time complexity: O(n), where n is the length of the input array. This is because we traverse the input array exactly once, and hash set operations (such as adding elements to the set and checking if an element is in the set) take O(1) time on average.
Space complexity: O(k), where k is the number of unique elements in the input array. This is because we store the unique elements in a hash set, which takes up memory proportional to the number of unique elements.

Approach 3: Using built-in set data structure:

Using the built-in set data structure in some programming languages.

Algorithm:

Convert the input array to a set to remove duplicates.
Convert the set back to a list and return the length of the list.

      
        public int RemoveDuplicates(int[] nums) {
            HashSet<int> set = new HashSet<int>(nums); // Initialize a hash set with the array elements
            int k = 0; // Initialize a variable k to 0
            foreach (int num in set) { // Iterate through the unique elements in the set
                nums[k] = num; // Copy the unique element to the new position at index k
                k++; // Increment k
            }
            return set.Count; // Return the number of unique elements
        }

      
        def removeDuplicates(self, nums: List[int]) -> int:
            unique_nums = set(nums) # Create a set of unique elements in the array
            nums[:len(unique_nums)] = sorted(unique_nums) # Overwrite the original array with the unique elements and sort them in ascending order
            return len(unique_nums) # Return the number of unique elements

      
        public int removeDuplicates(int[] nums) {
            Set<Integer> set = new HashSet<>();
            for (int num : nums) {
                set.add(num); // Add each element to the set (duplicates are automatically removed)
            }
            int k = 0; // Initialize a variable k to 0
            for (int num : set) {
                nums[k] = num; // Copy the unique element to the new position at index k
                k++; // Increment k
            }
            return set.size(); // Return the number of unique elements
        }

      
  
    int removeDuplicates(vector<int>& nums) {
        unordered_set<int> unique_nums(nums.begin(), nums.end()); // Create a set of unique elements in the array
        vector<int> result(unique_nums.begin(), unique_nums.end()); // Convert the set back to a vector
        nums = result; // Overwrite the original vector with the unique elements
        return unique_nums.size(); // Return the number of unique elements
    }

This approach creates a new hash set or set with the elements of the input array, which automatically removes duplicates. Then, we iterate through the unique elements in the set and copy them to the new position in the original array/vector. Finally, we return the number of unique elements in the set, which is equal to the size of the set. Since we are modifying the input array/vector in-place, we don't need to return a new array/vector.

This approach has a time complexity of O(n) or O(k log k) depending on the language and method used to create the set, where n is the length of the input array and k is the number of unique elements. The space complexity is O(k) to store the unique elements in the set.

Time complexity: O(n), where n is the length of the input array. This is because we traverse the input array exactly once, and set operations (such as adding elements to the set and checking if an element is in the set) take O(1) time on average.
Space complexity: O(k), where k is the number of unique elements in the input array. This is because we store the unique elements in a set, which takes up memory proportional to the number of unique elements.

Approach 4: Binary Search

Use binary search to find the location of each unique element and then copy it to the beginning of the array. This approach has a time complexity of O(n log n) and a space complexity of O(1).

Algorithm:

Initialize a variable k to 0.
Iterate through the array:
- If the value at index i is not equal to the value at index k, use binary search to find the location of the next unique element and copy it to the new position at index k.
- Increment k.
Return k.

      
     
        public int RemoveDuplicates(int[] nums) {
            int n = nums.Length; // Get the length of the array
            if (n == 0) { // If the array is empty, return 0
                return 0;
            }
            int k = 1; // Initialize a variable k to 1
            for (int i = 1; i < n; i++) { // Iterate through the array starting from index 1
                if (nums[i] != nums[i-1]) { // Check if the current element is different from the previous element
                    nums[k] = nums[i]; // Copy the current value to the new position at index k
                    k++; // Increment k
                }
            }
            return k; // Return the number of unique elements
        }

      
        def removeDuplicates(nums: List[int]) -> int:
            n = len(nums) # Get the length of the array
            if n == 0: # If the array is empty, return 0
                return 0
            k = 1 # Initialize a variable k to 1
            for i in range(1, n): # Iterate through the array starting from index 1
                if nums[i] != nums[i-1]: # Check if the current element is different from the previous element
                    nums[k] = nums[i] # Copy the current value to the new position at index k
                    k += 1 # Increment k
            return k # Return the number of unique elements

      
     
        public int removeDuplicates(int[] nums) {
            int n = nums.length; // Get the length of the array
            if (n == 0) { // If the array is empty, return 0
                return 0;
            }
            int k = 1; // Initialize a variable k to 1
            for (int i = 1; i < n; i++) { // Iterate through the array starting from index 1
                if (nums[i] != nums[i-1]) { // Check if the current element is different from the previous element
                    nums[k] = nums[i]; // Copy the current value to the new position at index k
                    k++; // Increment k
                }
            }
            return k; // Return the number of unique elements
        }

      
     
        int removeDuplicates(vector<int>& nums) {
            int n = nums.size(); // Get the length of the array
            if (n == 0) { // If the array is empty, return 0
                return 0;
            }
            int k = 1; // Initialize a variable k to 1
            for (int i = 1; i < n; i++) { // Iterate through the array starting from index 1
                if (nums[i] != nums[i-1]) { // Check if the current element is different from the previous element
                    nums[k] = nums[i]; // Copy the current value to the new position at index k
                    k++; // Increment k
                }
            }
            return k; // Return the number of unique elements
        }

Time complexity: O(n log n), where n is the length of the input array. This is because we perform binary search on each element in the input array, which takes O(log n) time, and we perform this operation n times in the worst case.
Space complexity: O(1), because we modify the input array in-place without using any extra memory.

Updated: Nov 5, 2023

« Candy Crush

Duplicate Zeros »