Remove Duplicates from Sorted Array Leetcode Solution

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Bloomberg Facebook Google LinkedIn Microsoft VMwareViews 10491

Problem Statement

The Remove Duplicates from Sorted Array Leetcode Solution – says that you’re given an integer array sorted in non-decreasing order. We need to remove all duplicate elements and modify the original array such that the relative order of distinct elements remains the same and, report the value of k which denotes the first k elements of the original array containing only distinct elements.

Note that after the first k elements, it doesn’t matter what the elements are, but the first k elements of the original array must contain all distinct elements of the input array with the relative order of distinct elements being the same.

Example:

Remove Duplicates from Sorted Array Leetcode Solution

 

Input: nums = [3,3,4,4]
Output: 2
nums = [3,4,_,_]

Explanation:

  • All unique elements are:- [3,4], Hence k = 2.
  • Fill all unique elements from the beginning of the input array keeping the relative order of unique elements the same.
  • [3,4,_,_] is the modified array where _ denotes any element.
  • Note that, we need to take care that all unique elements must be placed among the first k place of the input array.
Input: nums = [1,1,2]
Output: 2
nums = [1,2,_]

Explanation:

  • All unique elements are placed at the first 2 positions of the input array.
  • k = 2 is our answer.

Approach

Idea:

  1. The main idea is to solve this problem is to consider all subarrays one by one having the same elements.
  2. Keep an index k = 0, which states that the first k elements are already taken.
  3. Consider a subarray [i,j-1] where all elements have same value(x). Substitute nums[k] = x, and increment the index k by 1 since we are done with the current unique element and had placed this at the correct position. Also, change index i to j.
  4. Repeat step 2 until we’re done with all the unique elements.
  5. Finally, return k which is our answer (number of unique elements). Also, note that all unique elements are placed at first k positions and their relative order remains the same.

Code

Remove Duplicates from Sorted Array Leetcode C++ Solution:

class Solution {
public:
    int removeDuplicates(vector<int>& nums)
    {
        int k = 0,n = nums.size();
        for(int i=0;i<n;i++){
            int j = i;
            while(j<n and nums[i]==nums[j]){
                j++;
            }
            nums[k++] = nums[i];
            i = j -1;
        }
        return k;
    }
};

Remove Duplicates from Sorted Array Leetcode Java Solution:

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length,k = 0;
        for(int i=0;i<n;i++){
            int j = i;
            while(j<n && nums[i]==nums[j]){
                j++;
            }
            nums[k++] = nums[i];
            i = j - 1;
        }
        return k;
    }
}

Complexity Analysis for Remove Duplicates from Sorted Array Leetcode Solution

Time Complexity

The time complexity of the above code is O(N) since, we are iterating for every element twice, hence O(2N) = O(N).

Space Complexity

The space complexity of the above code is O(1) since we’re not taking any extra space like a vector or an array to solve this problem.

Reference: https://algodaily.com/lessons/using-the-two-pointer-technique

Translate »