Java two pointers solution O(n)


  • 2
    Z

    /**

    • Time complexity: Swap->O(1), One-pass->O(n)
    • Memory complexity: Two pointers, boolean->O(1)
      **/

    public class Solution {
    public int removeDuplicates(int[] nums) {

        //EDGE CASES
        if(nums == null) return 0;
        int length = nums.length;
        if(length <= 1) return length;
        
        //INIT TWO POINTERS
        //AND BOOLEAN TO JUDGE WHETHER THIS IS THE FISRT DUPLICATION OR NOT
        int i = 1;
        int j = 0;
        boolean first_duplication = false;
        
        //ONE-PASS SWAP
        while(i < length){
            if(nums[i] == nums[j] && first_duplication){
               while(i < length && nums[i]==nums[j]){
                  i++;
               }
               first_duplication = false;
            }else{
                first_duplication = (nums[i] == nums[j])?true:false;
                swap(nums,i,j+1);
                i++;
                j++;
            }
        }
        
        //RETURN NEW LENGTH
        return j+1;
    }
    
    //HELPER FUNCTION TO SWAP TWO ELEMENTS IN ARRAY
    public void swap(int[] nums,int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    

    }


  • 1
    F

    Easy to understand.
    No need for swap. Just overwrite the j+1 element.


  • 0
    Y

    why is this while(i < length && nums[i]==nums[j]){ i++;} necessary?


Log in to reply
 

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