Leetcode: Remove Duplicates from Sorted Array

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].

Analysis:
The question asks for removing duplicated elements from an array and return the new length. Note that the question requires for in place solution, which means you are not allowed to allocate extra space and store the truncated A into another array.

For e.g. For array A = [1, 1, 2], you should return length = 2, and A = [1, 2]. 

Solution:
The challenge part of this question is "compress" the array in-place. However, once an array is created, you are unable to change its length any more. As a result, the trick in this question is to remove the duplicates in the array without changing its length. How to do that? For e.g. For array A = [1, 1, 2] the "compressed" array is A = [1, 2, 2], and the "new" length is 2. 

As a result, you may get an idea. We can use two pointers. One points to the beginning of the duplicated elements, while the other points to the end of the duplicated elements, i.e, the next non-duplicated element. 

public class Solution {
    public int removeDuplicates(int[] A) {
        // if the array is empty or has only one element
        if (A.length < 2) return A.length;
        
        int i = 0;
        int j = 1;
        while (j < A.length) {
            if (A[i] == A[j]) j++;
            else {
                i++;
                A[i] = A[j];
                j++;
            }
        }
        return i + 1;
    }
}

Discussion:
We need to scan the array once so the time complexity is O(n). Since this method is in-place, the space complexity is O(1).

Summary:
The problem itself is not very difficult. But please be aware of the two pointers solution. Using two pointers is quite common is many array/string/linked list based problems. 

Update on 9/29/14:

public class Solution {
    public int removeDuplicates(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        int len = 0;
        for (int i = 1; i < A.length; i++) {
            if (A[i] != A[i - 1]) {
                A[++len] = A[i];
            }
        }
        
        return len + 1;
    }
}