Remove Duplicates from Sorted Array - LC26

Remove Duplicates from Sorted Array - LC26

ยท

4 min read

Table of contents

Question

Read the Question here https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/

Answer

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        int i = 0;
        for (int j = 1; j < nums.size(); j++) {
            if (nums[i] != nums[j]) {
                i++;
                nums[i] = nums[j];
            }
        }
        return i + 1;
    }
};

This algorithm will work only on sorted array .

The function take a vector of integer (as a reference) and return an integer length of modifies vector after removing the duplicate integer. The function start with a if condition which check if the vector is empty and if it is true it will return 0 , if it is false and there is elements in vector it will continue. The algorithm uses two pointer i and j which itreate over the vector and and check for duplicate integers. The pointer i starts with the first element and the for loop where j starts with second element. Inside the for loop, if statement check if index i element is not equal to index j element, and if this is the case, this mean the index j element is not duplicate of index i element , so the element j is assigned to i+1. Then the pointer i is increment with 1. This process continue till the end of the vector.

At the end of the function, the pointer i+1 is returned as the length of the modified vector after removing duplicates.

Its time complextity is O(n) as we are using only 1 for loop so the time complexity in depend on the size of the vector.

This is how I debug, you can go through it to see what is happening in the code.

vector -> 0 0 1 1 1 2 2 3 3 4
i=0    -> โ†‘
j=1    ->   โ†‘
if (0!=0) โŒ 
----------------------------------------
Vector -> 0 0 1 1 1 2 2 3 3 4
i=0    -> โ†‘
j=2    ->     โ†‘
if (0!=1) โœ…
    Vector -> 0 0 1 1 1 2 2 3 3 4
    i=1    ->   โ†‘
    nums[i] = nums[j]
    nums[1] = nums[2]
        0   =    1
    Vector modified (0 is replaced with 1)
                โ†“
    Vector -> 0 1 1 1 1 2 2 3 3 4
----------------------------------------
Vector -> 0 1 1 1 1 2 2 3 3 4
i=1    ->   โ†‘
j=3    ->       โ†‘
if (1!=1)โŒ
----------------------------------------
Vector -> 0 1 1 1 1 2 2 3 3 4
i=1    ->   โ†‘
j=4    ->         โ†‘
if (1!=1) โŒ
----------------------------------------
Vector -> 0 1 1 1 1 2 2 3 3 4
i=1    ->   โ†‘
j=5    ->           โ†‘
if (1!=2)โœ…
    Vector -> 0 1 1 1 1 2 2 3 3 4 
    i=2    ->     โ†‘
    nums[i] = nums[j]
    nums[2] = nums[5]
        1   =    2
    Vector modified (1 is replaced with 2)
                  โ†“
    Vector -> 0 1 2 1 1 2 2 3 3 4
----------------------------------------
Vector -> 0 1 2 1 1 2 2 3 3 4
i=2    ->     โ†‘
j=6    ->             โ†‘
if (2!=2) โŒ
----------------------------------------
Vector -> 0 1 2 1 1 2 2 3 3 4
i=2    ->     โ†‘
j=7    ->               โ†‘
if (2!=3)โœ…
    Vector -> 0 1 2 1 1 2 2 3 3 4 
    i=3    ->       โ†‘
    nums[i] = nums[j]
    nums[3] = nums[7]
        1   =    3
    Vector modified (1 is replaced with 3)
                    โ†“
    Vector -> 0 1 2 3 1 2 2 3 3 4
----------------------------------------
Vector -> 0 1 2 3 1 2 2 3 3 4
i=3    ->       โ†‘
j=8    ->                 โ†‘
if (3!=3) โŒ
----------------------------------------
Vector -> 0 1 2 3 1 2 2 3 3 4
i=3    ->       โ†‘
j=9    ->                   โ†‘
if (3!=4)โœ…
    Vector -> 0 1 2 3 1 2 2 3 3 4 
    i=4    ->         โ†‘
    nums[i] = nums[j]
    nums[4] = nums[9]
        1   =    4
    Vector modified (1 is replaced with 4)
                      โ†“
    Vector -> 0 1 2 3 4 2 2 3 3 4
----------------------------------------
For Loop Stop
----------------------------------------

Answer
Vector -> 0 1 2 3 4 2 2 3 3 4
return i+1 = 5

Did you find this article valuable?

Support Jyotirmoy Barman by becoming a sponsor. Any amount is appreciated!