LeetCode Easy: Remove Duplicates from Sorted Array

An easy level problem on LeetCode - Remove Duplicates from Sorted Array (https://leetcode.com/problems/remove-duplicates-from-sorted-array/)

 

 

 

APPROACH 1:

 

I wrote a quick and easy solution in C++ for this easy level problem some years back - Single pass and O(n), ignoring all duplicates as we go:

class Solution {
public:
    int removeDuplicates(vector& nums) {
        int len = nums.size();
        if (len<=1)
            return len;
        
        int i, top;
        for (i=1, top=1; i<len; i++)
        {
            if (nums[i] != nums[top-1])
                nums[top++] = nums[i];
        }
        
        return top;
    }
};

 

 

 

APPROACH 2:

 

A couple of dys back, I revisited this problem, in Java, but this time, I looked at it and instantly came to my mind, an even more optimised version of it, O(lg m) in time complexity, where, m = number of unique elements in the input list, making use of predicate based binary searching technique to get the last occurrence of a particular element in the left part of the current index:

 

Here’s how the solution goes for it:

 

class Solution {
    public int removeDuplicates(int[] nums) {
        int reducedLen = -1;
        if (nums.length == 0)
            return reducedLen+1;
        
        int pos = 0;
        while (pos < nums.length) {
            pos = getLastOccurenceIdx(nums, pos);
            nums[++reducedLen] = nums[pos];
            pos++;
        }
        
        return reducedLen+1;
    }
    
    private int getLastOccurenceIdx(int[] nums, int firstPos) {
        int min = firstPos;
        int max = nums.length-1;
        while (min < max) {
            int mid = min + (max-min+1)/2;
            if (nums[mid]>nums[firstPos]) {
                max = mid-1;
            } else {
                min = mid;
            }
        }
        return min; 
    }
}

 

 

Do share if better solutions cross your mind!

Happy Coding, until next spree!!