Remove duplicates from sorted array

Intuition

The naive way is to think of a data structure that does not store duplicate elements, that is HashSet. Keep track of unique elements in hashset, and at last copy all the elements from the HashSet to the original array.

Approach

Declare a HashSet and traverse the array by putting every element of the array in the HashSet

Store size of the set in a variable K. Now put all elements of the set in the array from the starting of the array and finally return K

Solution

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to remove duplicates from the array
    int removeDuplicates(vector<int>& nums) {
        
        /* Set data structure to store unique 
        elements maintaining the sorted order */
        set<int> s;
        
        // Add all elements from array to the set
        for (int val : nums) {
            s.insert(val);
        }
        
        // Get the number of unique elements
        int k = s.size();
        
        int j = 0;
        // Copy unique elements from set to array
        for (int val : s) {
            nums[j++] = val;
        }
        
        // Return the number of unique elements
        return k;
    }
};

// Helper function to print first n elements of the array
void printArray(vector<int> &nums, int n) {
    for(int i=0; i < n; i++) {
        cout << nums[i] << " ";
    }
    cout << endl;
}

int main() {
    vector<int> nums = {1, 1, 2, 2, 2, 3, 3};
    
    cout << "Original Array: ";
    printArray(nums, nums.size());
    
    // Create an instance of the Solution class
    Solution sol;
    
    // Function call to remove duplicates from array
    int k = sol.removeDuplicates(nums);
    
    cout << "Array after removing the duplicates: ";
    printArray(nums, k);
    
    return 0;
}
import java.util.*;

class Solution {
    // Function to remove duplicates from the array
    public int removeDuplicates(int[] nums) {
        
        // TreeSet to store unique elements in sorted order
        Set<Integer> s = new TreeSet<>();
        
        // Add all elements from array to the set
        for (int val : nums) {
            s.add(val);
        }
        
        // Get the number of unique elements
        int k = s.size();
        
        int j = 0;
        // Copy unique elements from set to array
        for (int val : s) {
            nums[j++] = val;
        }
        
        // Return the number of unique elements
        return k;
    }
}

class Main {
    // Helper function to print first n elements of the array
    public static void printArray(int[] nums, int n) {
        for (int i = 0; i < n; i++) {
            System.out.print(nums[i] + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        int[] nums = {1, 1, 2, 2, 2, 3, 3};
        
        System.out.print("Original Array: ");
        printArray(nums, nums.length);
        
        // Create an instance of the Solution class
        Solution sol = new Solution();
        
        // Function call to remove duplicates from array
        int k = sol.removeDuplicates(nums);
        
        System.out.print("Array after removing the duplicates: ");
        printArray(nums, k);
    }
}
class Solution:
    # Function to remove duplicates from the array
    def removeDuplicates(self, nums):
        
        # Set data structure to store unique elements
        s = set()
        
        # Add all elements from array to the set
        for val in nums:
            s.add(val)
        
        # Get the sorted list of unique elements
        sorted_unique = sorted(s)
        
        # Copy unique elements from sorted list to array
        for j in range(len(sorted_unique)):
            nums[j] = sorted_unique[j]
        
        # Return the number of unique elements
        return len(sorted_unique)

# Helper function to print first n elements of the array
def printArray(nums, n):
    for i in range(n):
        print(nums[i], end=" ")
    print()

if __name__ == "__main__":
    nums = [1, 1, 2, 2, 2, 3, 3]
    
    print("Original Array: ", end="")
    printArray(nums, len(nums))
    
    # Create an instance of the Solution class
    sol = Solution()
    
    # Function call to remove duplicates from array
    k = sol.removeDuplicates(nums)
    
    print("Array after removing the duplicates: ", end="")
    printArray(nums, k)
class Solution {
    // Function to remove duplicates from the array
    removeDuplicates(nums) {
        
        // Set data structure to store unique elements
        let s = new Set();
        
        // Add all elements from array to the set
        for (let val of nums) {
            s.add(val);
        }
        
        // Get the number of unique elements
        let k = s.size;
        
        let j = 0;
        // Copy unique elements from set to array
        for (let val of s) {
            nums[j++] = val;
        }
        
        // Return the number of unique elements
        return k;
    }
}

// Helper function to print first n elements of the array
function printArray(nums, n) {
    for (let i = 0; i < n; i++) {
        process.stdout.write(nums[i] + " ");
    }
    console.log();
}

// Example usage
let nums = [1, 1, 2, 2, 2, 3, 3];

console.log("Original Array: ");
printArray(nums, nums.length);

// Create an instance of the Solution class
let sol = new Solution();

// Function call to remove duplicates from array
let k = sol.removeDuplicates(nums);

console.log("Array after removing the duplicates: ");
printArray(nums, k);

Complexity Analysis

Time Complexity: O(N * log N) + O(N), for using hashset, it will take O(N * log N) and also to traverse the array once O(N). Here N is the size of the array. Space Complexity: O(N) because in the worst case, all the elements of the array can be unique and it will take O(N) space. Here N represents the size of the array.

Intuition

Imagine you have a shelf where you keep your favorite books, and these books are sorted in alphabetical order. Over time, you notice that some books are repeated multiple times, and you want to organize the shelf so that each book title appears only once. Additionally, you don't want to change the order of the unique books on your shelf.

Here's what you would do:

Start at the beginning of the shelf and pick the first book. Look at the next book, if it's the same as the one just picked, then move on to the next book. If the next book is different, keep it next to the first book that is picked. Repeat this process for all books on the shelf.

Once all the books are checked, the first part of the shelf will have all the unique books in their original order. The rest of the books on the shelf don't matter, so ignore them.

Approach

Initialize 2 variables i as 0 and variable j as 1, where i will track the position of the last unique element found and j will iterate through the array to find new unique elements.

Iterate in array using j from second element to the end of the array.

If the element at position j is different from the element at position i, it means a new unique element is found. This is because the array is sorted in non-decreasing order, so any new element that is different from the previous one must be unique.

When a new unique element is found, increment i to move to the next position for storing unique elements. Copy the element at position j to the new position at i. This ensures that the first i + 1 elements of the array are all unique.

Continue comparing elements and updating the array until j has iterated through the entire array. Once the loop completes, the value of i + 1 represents the number of unique elements in the array.

Dry Run

Solution

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to remove duplicates from the vector
    int removeDuplicates(vector<int>& nums) {
        // Edge case: if vector is empty
        if (nums.empty()) {
            return 0;
        }
        
        // Initialize pointer for unique elements
        int i = 0;
        
        // Iterate through the vector
        for (int j = 1; j < nums.size(); j++) {
            /*If current element is different 
            from the previous unique element*/
            if (nums[i] != nums[j]) {
                /* Move to the next position in 
                the vector for the unique element*/
                i++;
                /* Update the current position 
                with the unique element*/
                nums[i] = nums[j];
            }
        }
        
        
        // Return the number of unique elements
        return i+1;
    }
};

int main() {
    vector<int> nums = {1, 1, 2, 2, 2, 3, 3};
    
    // Create an instance of the Solution class
    Solution solution;
    
    // Call removeDuplicates to remove duplicates from nums
    int k = solution.removeDuplicates(nums);
    
    cout << "The vector after removing duplicate elements is " << endl;
    for (int i = 0; i < k; i++) {
        cout << nums[i] << " ";
    }
    cout << endl;
    
    return 0;
}
import java.util.*;

class Solution {
    // Function to remove duplicates from the array
    public int removeDuplicates(int[] nums) {
        // Edge case: if array is empty
        if (nums.length == 0) {
            return 0;
        }
        
        // Initialize pointer for unique elements
        int i = 0;
        
        // Iterate through the array
        for (int j = 1; j < nums.length; j++) {
            /*If current element is different 
            from the previous unique element*/
            if (nums[i] != nums[j]) {
                /* Move to the next position in 
                the array for the unique element*/
                i++;
                /* Update the current position 
                   with the unique element*/
                nums[i] = nums[j];
            }
        }
        
        // Return the number of unique elements
        return i + 1;
    }
}

public class Main {
    public static void main(String[] args) {
        int[] nums = {1, 1, 2, 2, 2, 3, 3};
        
        // Create an instance of the Solution class
        Solution solution = new Solution();
        
        // Call removeDuplicates to remove duplicates from nums
        int k = solution.removeDuplicates(nums);
        
        System.out.println("The array after removing duplicate elements is ");
        for (int i = 0; i < k; i++) {
            System.out.print(nums[i] + " ");
        }
        System.out.println();
    }
}
from typing import List

class Solution:
    # Function to remove duplicates from the list
    def removeDuplicates(self, nums: List[int]) -> int:
        # Edge case: if list is empty
        if not nums:
            return 0
        
        # Initialize pointer for unique elements
        i = 0
        
        # Iterate through the list
        for j in range(1, len(nums)):
            """ If current element is different 
            from the previous unique element"""
            if nums[i] != nums[j]:
                
                """ Move to the next position in 
                the list for the unique element"""
                i += 1
                
                """ Update the current position 
                with the unique element"""
                nums[i] = nums[j]
        
        # Return the number of unique elements
        return i + 1

# Main function to test the implementation
if __name__ == "__main__":
    nums = [1, 1, 2, 2, 2, 3, 3]
    
    # Create an instance of the Solution class
    solution = Solution()
    
    # Call removeDuplicates to remove duplicates from nums
    k = solution.removeDuplicates(nums)
    
    print("The list after removing duplicate elements is ")
    for i in range(k):
        print(nums[i], end=" ")
    print()
class Solution {
    // Function to remove duplicates from the array
    removeDuplicates(nums) {
        // Edge case: if array is empty
        if (nums.length === 0) {
            return 0;
        }
        
        // Initialize pointer for unique elements
        let i = 0;
        
        // Iterate through the array
        for (let j = 1; j < nums.length; j++) {
            /* If current element is different 
            from the previous unique element*/
            if (nums[i] !== nums[j]) {
                
                /* Move to the next position in 
                the array for the unique element*/
                i++;
                
                /* Update the current position 
                with the unique element*/
                nums[i] = nums[j];
            }
        }
        
        // Return the number of unique elements
        return i + 1;
    }
}

// Main function to test the implementation
if (typeof require !== 'undefined' && require.main === module) {
    let nums = [1, 1, 2, 2, 2, 3, 3];
    
    // Create an instance of the Solution class
    let solution = new Solution();
    
    // Call removeDuplicates to remove duplicates from nums
    let k = solution.removeDuplicates(nums);
    
    console.log("The array after removing duplicate elements is ");
    for (let i = 0; i < k; i++) {
        process.stdout.write(nums[i] + " ");
    }
    console.log();
}

Complexity Analysis

Time Complexity: O(N), for single traversal of the array, where N is the size of the array. Space Complexity: O(1), not using any extra space.

Problem List

Remove duplicates from sorted array

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Solution

Complexity Analysis

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code