Remove Duplicates from Sorted Array

Series: Exploring Algorithms

Table of Contents

Beginning of the series

This is the first post from the series: Exploring Algorithms. The set of posts will include an exploration of different algorithms and techniques to solve various problems.

In addition to the theory, I will also write about the implementations of each algorithm in different programming languages. Some of the languages that I have in mind are Java, C, C++, Python, and Golang.

From this initiative, I intend to not just learn about the algorithms, but also how they can be implemented in different languages, hence learning more about programming languages as well.

Each post in this series will contain content in the following structure:

algorithm
├── Introduction
├── Some example use cases
├── Pseudocode
└── Implementations
    ├── Java
    ├── C
    ├── C++
    ├── Python
    └── JavaScript

Let’s begin with our first problem.

Problem statement

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Link to the problem on leetcode: https://leetcode.com/problems/remove-duplicates-from-sorted-array/

Notes

  • Simple solution:
    • Algorithm:
      • Add all elements to a sorted set (like TreeSet in Java)
      • Set the first n numbers of the array to the elements in set
      • Return the size of set
    • Complexity:
      • Time: O(n)
      • Space: O(n)
    • Disadvantage:
      • space complexity should be constant
  • Final solution:
    • Algorithm Implemented below
    • Complexity:
      • Time: O(n)
      • Space: O(1)

Pseudocode

Initialize variables ans, i, j to 0
while i is less than the array length:
    Initialize current variable to the value of ith element in nums array
    Increment ans
    Set jth element to current
    while i is less than array length and current is equal to ith element:
        increment i
    increment j
Return ans variable

Time complexity: O(n)

Implementations

Java

class Solution {
    public int removeDuplicates(int[] ar) {
        int ans = 0;
        int i = 0, j = 0;
        while (i < ar.length) {
            int current = ar[i];
            ans++;
            ar[j] = current;
            while (i < ar.length && current == ar[i]) {
                i++;
            }
            j++;
        }
        return ans;
    }
}

C

int removeDuplicates(int* nums, int numsSize) {
    int i, ans, j, current;
    i = 0;
    j = 0;
    ans = 0;
        
    while (i < numsSize) {
        current = nums[i];
        nums[j] = current;
        ans++;
        while (i < numsSize && current == nums[i]) i++;
        j++;
    }
    
    return ans;
}

C++

class Solution {
public:
    int removeDuplicates(vector<int>& ar) {
        int ans = 0;
        int i = 0, j = 0;
        while (i < ar.size()) {
            int current = ar[i];
            ar[j] = current;
            ans++;
            while (i < ar.size() && current == ar[i]) i++;
            j++;
        }
        return ans;
    }
};

Python

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans, i, j = 0, 0, 0
        while i < len(nums):
            current = nums[i]
            ans += 1
            nums[j] = current
            while i < len(nums) and current == nums[i]:
                i += 1
            j += 1
        return ans        

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    var ans = 0, i = 0, j = 0, current;
    while (i < nums.length) {
        current = nums[i];
        nums[j] = current;
        ans++;
        while (i < nums.length && current == nums[i]) i++;
        j++;
    }
    return ans;
};

Other posts in this series:

Series: Exploring Algorithms

comments powered by Disqus