Coding

Remove Duplicates from Sorted Array Solution

5
(1)

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.

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).

Constraints:

1 <= nums.length <= 3 * 104
-100 <= nums[i] <= 100
nums is sorted in non-decreasing order.




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).
Constraints:

1 <= nums.length <= 3 * 104
-100 <= nums[i] <= 100
nums is sorted in non-decreasing order.



One constraint that we have is that we have to modify the array in place and cannot create another array. There can be two approaches that you can take to solve this problem.

One approach would be where you can create a bitset. Then you can iterate through the input array and set corresponding bits of the bitset to true. Since the numbers can be negative as well (-100 to 100), so you can add 100 to the number while setting the bit to true. And then you can iterate through this bitset and wherever you find bit set to true, you subtract 100 from that bit index and then set an element in the array with the result. The code for this approach is in removeDuplicates1 method. While this approach is very space efficient, we can do better in terms of time efficiency.

A better approach would be as following. You can use the two pointers approach. Here you can have a left pointer and right pointer both initially pointing to beginning of the number array. Now you keep moving the right pointer to next element. When you find numbers at left pointer and right pointer to be equal, you continue the loop. But when you find numbers at left pointer and right pointer to be different, then you move left pointer to next element and then assign it value of right pointer. When the right pointer reaches the end of array, you are basically done. Now all the elements till left pointer are now sorted non duplicate elements. So you can return index of left pointer + 1. Although it takes a lot of lines to explain this, the coding logic is relatively simple. This code approach is faster than above and is illustrated in removeDuplicates method.

class Solution {
   
    public int removeDuplicates(int[] nums) {
        
        int left = 0;        
        for (int right = 0; right<nums.length; right++) {
            if (nums[left] == nums[right]) {
                continue;
            }
            left++;
            nums[left] = nums[right];
        }
        return left+1;
    }
    
    public int removeDuplicates1(int[] nums) {
        
        BitSet bitSet = new BitSet(201);
        for (int i=0; i<nums.length; i++) {
            bitSet.set(nums[i]+100);
        }
        int numsIndex = 0;
        for (int i=0; i<bitSet.length(); i++) {
            if (bitSet.get(i)) {
                nums[numsIndex++] = i-100; 
            }
        }
        
        return numsIndex;
    }
}

How useful was this post?

Click on a star to rate it!

Average rating 5 / 5. Vote count: 1

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?