Is it possible to solve this question in place?


  • 1
    M

    I submitted an answer based on a new Array B. I scan the Array A and only put the first 1-2 of the same numbers to B. Then copy the B back to A.

    It requires O(N) space. Is there any way to solve this question with O(1) space?


  • 10
    M

    Yes, there is a way. Since you are returning the length of the array at the end, anything at the end of the array beyond the length you return is not considered part of your answer. Therefore, as you traverse the array, you can copy the next valid item into spots where there are 3 or more of an element in a row. This will duplicate further items, but as long as you keep moving the elements forward, the duplicates will be beyond the length you return.

    In Java, here is my answer using this algorithm, using O(n) time and O(1) space:

    public int removeDuplicates(int[] A) {
            if(A.length < 3) return A.length;
            int count = 0;
            int idx=0;
            for(int i=1;i<A.length;i++){
                if(A[idx] == A[i])
                    count++;
                else
                    count = 0;
    
                if(count < 2)
                    idx++;
    
                A[idx] = A[i];
            }
            return idx+1;
        }

  • 92
    D

    It's possible to do that. Here is my solution with comments. Only one if statement is used in loop.

    /**
     * Solution:
     * Only difference is now we allow two duplicates. So we scan through the 
     * array and if we find the 3rd duplicate we just skip them.
     * We know it's 3rd duplicate by comparing the itor with second last elements in
     * final array (if A[itor] == A[len-2], then A[itor]==A[len-2]==A[len-1])
     */
    int removeDuplicates(int A[], int n) {
        if (n <= 2) return n;       // no need to deal with n<=2 case.
        int len = 2, itor = 2;
        while (itor < n) {
            if (A[itor] != A[len-2]) 
                A[len++] = A[itor];
            itor++;
        }
        return len;
    }

  • 0
    D
    This post is deleted!

  • 0
    S

    Answers you've written must describe your code with more detail content. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.


  • 0
    Q

    Really Smart.


  • 0
    U

    Nice, this is actually a general solution to remove duplicates from sorted array with at most k(>0) duplicates kept.


  • 4
    O

    This is a version in Python, with removals. Very simple. I iterated from the end of the array to make sure that item removals didn't effect future duplication checks.

    def removeDuplicates(A):
        if (len(A) <= 3): return len(A)
        for i in range(2,len(A))[::-1]:
            if A[i] == A[i-2]:
                del A[i]
        return len(A)

  • 0
    F

    this is really smart


  • 0
    J

    In your version, an element may be copied many times.


  • 1
    Z

    Here is my in-place solution for this question:

    int removeDuplicates(int A[], int n) {
        if(n <= 2) return n;
        
        int k = 0;  bool trigger = false;
        for(int i = 1; i < n; i++)
            if(A[i] != A[k]) {
                A[++k] = A[i];   trigger = false;
            }
            else if (!trigger) {
                A[++k] = A[i];   trigger = true;
            }
            
        if(++k < n)   A[k] = '\0';
        return k;
    }
    

  • 0
    L
    public int removeDuplicates(int[] A) {
        if(A.length <= 2) return A.length;
        int length = 2;
        for(int i = 1; i < A.length - 1; i++) {
            if((A[i] != A[i+1])||(A[i] != A[length-2])) {
                A[length++] = A[i+1];
            }
        }
        return length;
    }

  • 0
    G

    nice,learned


  • 0
    L

    really smart, only need to compare the 2nd element, cool.

    you use the sorted condition better than others. smarter.


  • 0
    C

    wow, that's just elegant!


  • 0
    W

    It is really helpful! Wonderful!


  • 0
    M

    Very nice solution. I think that you only need the assignment for the "if (count < 2)" conditional, i.e. "A[++idx] = A[i]".


  • 1
    F

    the same idea as dragonmigo, improved a little on corner case.

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

  • 0
    L

    you are really smart


  • 0
    O

    nice solution! killer observation!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.