LeetCode Remove Duplicates from Sorted Array I and II: O(N) Time and O(1) Space

Overview

LeetCode Remove Duplicates from Sorted Array I and II can be solved in O(N) Time, O(1) Space by using two pointers to remove duplicates on the fly while scanning.

LeetCode Remove Duplicates from Sorted Array I and II:

(1) Given a sorted array, 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 in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

(2)  Follow up for “Remove Duplicates”:

What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

Analysis: O(N) Time and O(1) Space

Linear scan through the array and store those not duplicated elements in the already scanned part of the original array. More specifically, check whether A[i] == A[i-1], if equal, we skip A[i], if not we store A[i] in previous positions of A (use the length of the new array to keep the position). For the follow up, you need a count variable to keep how many times the duplicated element appears, if you encounter a different element, just set counter to zero, if you encounter a duplicated one, you need to check this count, if it is already 1, then you need to skip it, if it is still 0, then you could keep this element. The following code is accepted by the leetCode OJ to pass these  Remove Duplicates from Sorted Array I and II problem:

class Solution {
    public:
        int removeDuplicates(int A[], int n) {
            if (n < 1)
                return n;

            int i = 0, j = 1;
            while (j < n) {
                if (A[j] != A[j - 1])
                A[++i] = A[j];
                ++j;
            }
            return i + 1;
        }
};

And the following is for the follow up question:

int removeDuplicates(int A[], int n) {
    if (n < 2)
        return n;

    int i = 1, j = 1;
    bool twice = false;

    while (j < n) {
        if (A[j] != A[j-1]) {
            A[i++] = A[j];
            twice = false;
        }
        else {
            if (!twice) {
                A[i++] = A[j];
                twice = true;
            }
        }
        ++j;
    }
    return i;
}

Extension: 

  1. What if the number of duplicates are allowed to appear k times? Can you write a consistent API to solve this general problem?
  2. Similar approach could be utilized to remove all the digits from a string, can you implement it?

The following code is my implementation for the general k times problem and I will leave the second one to the readers themselves to solve it:

int removeDuplicates(int A[], int n, int k) {
            if (n <= k) 
                return n;

            int i = 1, j = 1;
            int cnt = 1;
            while (j < n) {
                if (A[j] != A[j-1]) {
                    cnt = 1;
                    A[i++] = A[j];
                }
                else {
                    if (cnt < k) {
                        A[i++] = A[j];
                        cnt++;
                    }
                }
                ++j;
            }
            return i;
        }

Summary

LeetCode Remove Duplicates from Sorted Array I and II can be solved in O(N) Time, O(1) Space by using two pointers to remove duplicates on the fly while scanning.

Written on April 18, 2013