Easy to understand java solution without ++i pointers


  • 0
    K

    All these ++i pointers got me confused, so I did my own solution. It still runs in O(n) time and O(1) space.

    The trick for this one is to have a "faster" point that moves one index at a time, but skips over duplicates when it encounters them. Then, the slower pointer(in this case i) will simply update the current position in the array with whatever value the faster pointer has. Since the faster pointer will always be pointing to the next non-duplicated entry, this will always work.

    Solution below. Cheers!

    public class Solution {
       public int removeDuplicates(int[] nums) {
         if (nums.length == 0) {
               return 0;
         }
         
         //First we iterate through the whole array to get the number of duplicates. I'm sure this could be put in the for loop below, but I was too lazy to figure it out with all the edge cases.
         int dups = 0;
         for (int i = 1; i < nums.length; i++) {
             if (nums[i - 1] == nums[i]) {
                 dups++;
             }
         }
         
         //We start at index one, because obviously, there won't be any duplicates with just 1 element.
         int fasterIndex = 1;
         for (int i = 1; i < nums.length; i++) {
             //Condition check for duplicates. Obviously we don't want to run out of the array, so we also check against length.
             while (fasterIndex  + 1 < nums.length && nums[fasterIndex] == nums[fasterIndex - 1]) {
                 fasterIndex++;
             }
             
             nums[i] = nums[fasterIndex];
             //We still want the faster point to move once after every assignment(otherwise it wouldn't move when there are no duplicates!), so that's what this if is doing here. We check against the end of the array as well
             if (fasterIndex + 1 < nums.length) {
                fasterIndex++;
             }
             
         }
    
         return nums.length - dups;
       }
    
    }
    

Log in to reply
 

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