Leetcode–Remove Duplicates from Sorted Array

The Problem:

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

Notes:

  1. Do it inplace–> two pointers
  2. Two pointer method with one point to the index of comparing with previous, and one point to the index of where next replace will happen. Pointer advance condition: move comparing index forward anyway, move replace index forward when comparing result show not same as previous

Java Solution:

public class Solution {
    public int removeDuplicates(int[] A) {
        if(A.length <=1)return A.length;
        int prev = A[0];
        int replace = 1;
        for(int i = 1; i < A.length; i++){
            if(A[i]!=prev){
                prev = A[i];
                if(replace < i){
                    A[replace] = A[i];
                    
                }
                replace++;
            }
        }
        return replace;
    }
}
Advertisements

One thought on “Leetcode–Remove Duplicates from Sorted Array

  1. Pingback: Leetcode–Remove Duplicates from Sorted Array II | Linchi is coding

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s