Monday, June 5, 2017

Remove duplicates from the sorted array

Problem Statement

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 nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.



def remove_dup_sorted(A):
    if not A:
        return 0
    for i in range(1,len(A)):
         if A[i] != A[newTail]:
            newTail +=1
    return newTail +1


Link to GitHub  : Code
  • We need 2 variables i and id. i would be used for looping and id would be used for moving the position
  • if we find the duplicates we need to move the position of the value and then return id

 //Time O(1) Space O(1)
 public static int get(int arr [], int n)
  //The length is less than 2 than return
  if(n < 2) 
  {return n;}
        int id = 1;
        for(int i = 1; i < n; ++i) {
            if(arr[i] != arr[i-1]) 
            {arr[id++] = arr[i];}
        return id;

No comments:

Post a Comment