Back to Two Pointers
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. Then return the number of unique elements in `nums`.
Examples
Input:nums = [1,1,2]
Output:2, nums = [1,2,_]
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.
Constraints
1 <= nums.length <= 3 * 10^4-100 <= nums[i] <= 100nums is sorted in non-decreasing order.
Approach
Iterate through the array and add elements to a hash set to track unique values. Since sets do not guarantee order, we can also use an extra list to keep the relative order of the first occurrence of each element. Finally, overwrite the original array with these unique elements.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
This approach uses O(n) extra space and does not solve the problem "in-place" as requested by the problem description.
Solution.java
class Solution { public int removeDuplicates(int[] nums) { if (nums.length == 0) return 0; List<Integer> unique = new ArrayList<>(); Set<Integer> seen = new HashSet<>(); for (int num : nums) { if (!seen.contains(num)) { seen.add(num); unique.add(num); } } for (int i = 0; i < unique.size(); i++) { nums[i] = unique.get(i); } return unique.size(); }}