Java O(n) time and O(1) space - running offset


  • 0
    C

    This solution is what I came up with. There is a offset value, length value (count), and current integer value. If the current spot in the array matches the cur value then you increment the offset and subtract from the length of the array. If no match is found, you have a unique integer. Update the current integer value and the new value gets placed into the correct spot of the array. This is done by keeping track of the offset value. For example in the array [1,2,2,3]... when you get to the 4th element (integer 3). Your offset will be 1 because there was 1 duplicate. The 4th element then goes into the i-offset spot in the array (4-1). The resulting array is [1,2,3,3] with a length of 3 (causing the problem to skip the 4th element).

        int count = A.length;
        int cur = Integer.MIN_VALUE;
        int offset = 0;
        for(int i = 0; i <A.length;i++){
            if(offset >= A.length) break;
            if(A[i] == cur){
                offset++;
                count--;
            }
            else{
                A[i-offset] =A[i];
                cur = A[i];
            }
        }
        return count;
    

    The only problem I see is if the first value in the array is the Integer.MIN_VALUE. I am not sure how to fix this. If I make it Integer.MAX_VALUE then if the first element in the array is the MAX_VALUE it will also cause an issue. Any thoughts?


Log in to reply
 

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