Monday, April 26, 2010

Remove duplicates from the sorted array

Problem 
 Remove duplicates from the sorted array
Example
[1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5] -> [1, 2, 3, 4, 5]

Method 1- using 3 pointers

//using 3 pointers
fixDuplicatesInSortedArray(Integer[] a):
    start = 0
    end = 0
    destination = 0

    while(start < a.length):
        while(end < a.length && a[end] == a[start]):
            end++
        end--
       
        //copy the distinct element
        a[destination] = a[start]
        destination++
       
        start = end + 1
        end = start

    //null out the rest
    while destination < a.length:
        a[destination] = null

    return

Method 2 - using 2 pointers

//using 2 pointers
fixDuplicatesInSortedArray(Integer[] a):
    prev = 0
    curr = 1
   
    while curr < a.length():
        while curr < a.length && a[curr] == c[prev]:
            curr++
        if curr == a.length() break
       
        prev++
        a[prev] = a[curr]
        curr++
   
    //null out the rest
    prev++
    while prev < a.length:
        a[prev] = null
   
    return

Time complexity - O(n) in both cases.

Thanks.

0 comments:

Post a Comment