My C++ solution with O(n) and avoid the self copy


  • 0
    V

    I barely use any extra space and the answer should be O(n) such that the array is sorted.

    class Solution {
    public:
        int removeDuplicates(int A[], int n) {
           if (n == 0) return 0;
        
           int *push_ptr = A;
           int *incre_ptr = push_ptr + 1;
        
            // O(n)
            for (int i = 1; i != n; i++, incre_ptr++) 
            {
                if (*incre_ptr != *push_ptr && incre_ptr != ++push_ptr)
                {
                    *push_ptr = *incre_ptr;
                }
            }
        
            return push_ptr - A + 1;
        }
    };

Log in to reply
 

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