kevin074

Posted on

# Leetcode diary: 80. Remove Duplicates from Sorted Array II

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

This question was just the right medium level.

Given a sorted array, remove any extra elements after 2 repetitions. You have to do this in place, and also return k.
k = the index starting from which all the extras resides. Whatever value after k is unimportant so it can be anything as long as before k all the elements retain their sorted order with at most 2 reptitions.

Note that you NEED to return k at the end of the function.
the test code will check if the input array is correctly handled.

[1,1,1,2,2,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,5]
= [1,1,2,2,3,3,4,4,5], k = 9

The first thing you should notice that you can't really just do:
k = (number of unique integers) * 2, since any integer can be count of 1.

However that's easy to do, you can just loop through the array, keep a map with integer as key and value as counts. You don't increment past 2. Return the sum of the counts at the end.

What you can also do while looping through the array is to change all the extra values into some signal that it's extra, I chose NaN since I code in javascript.

Next, you need to loop through the array again, this time you want to swap the values with the NaN in place so that all the NaNs are in the end of the array.

At this point you need to be careful with how you swap, I didn't get this right the first time so it's the mental gymnastics is still a bit too much for me.
what can happen is
1.) NaN hits a bunch of integers in a row, so needs to swap with each, this is sort of easy since it's just
swap(array, indexNaN, indexInteger);
indexInteger = indexNaN;

2.) NaN hits a bunch of NaNs before hitting after integer.
This part is what tricks me up. Obviously you would just ignore the bunch of NaNs, however if you do indexInteger = indexNaN, then the next integer you swap with will just be at the end of the NaN chain.

At this point, the key revelation is that once you hit the chain, every time you swap, the "head" of the NaN chain is just the next index. What you are doing is swapping the head with tail, then making the head = head.next (like listNodes).

Now you need to revisit case 1, is that true and what happens when you hit bunch of NaNs then bunch of integers. Turns out since the NaN chain grows toward the end while integer chain grows from the head, it's literally always just indexNaN = indexNaN+1. It's just that simple lol...

full code below, with notes that I wrote while solving this, don't have to read it though, mostly just repeat what I wrote already but might be nice for you to see where I was wrong.

``````var removeDuplicates = function(nums) {
const countMap = {};
nums.forEach(function(val, index){
val in countMap ? countMap[val]++ : countMap[val] = 1;
if(countMap[val] > 2) {
countMap[val] = 2
nums[index] = NaN;
}
});

let lastNaNIndex = -1;

nums.forEach(function(val, currentIndex){
if(isNaN(val) && lastNaNIndex === -1) {
lastNaNIndex = currentIndex;
return;
}

if (lastNaNIndex > -1 && !isNaN(val)) {
swap(nums, lastNaNIndex, currentIndex)
lastNaNIndex = lastNaNIndex+1;
}
})

return Object.values(countMap).reduce(function(total, val){
},0)
};

function swap (nums, i,j) {
const temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}

// [1,1,NaN,2,3,3,NaN,NaN,NaN,4]
// pass
// pass
// lastNaNIndex = 2
// swap 2 with lastNaNIndex, lastNaNIndex = 3
// swap 3 with lastNaNIndex, lastNaNIndex = 4
// swap 3 with lastNaNIndex, lastNaNIndex = 5
// return for all the NaNs
// swap 4 with lastNaNIndex = 5

/*
so the question is saying given a sorted array with repeated numbers,
for each number, remove any extra more than 2 reptitions
this has to be done in place, so everything pushed to the back
we are to return k, where k = number of elements in array with <=2 reptitions
and the array itself, with elementers after k to be in anything

[4,4,4,4,4,4,5,5,5,7,7,7,11,11,11]
k=10, [4,4,5,5,7,7,11,11 ...]

the first thing we know is that k is easy to obtain
we run a loop through the array
via a map, we remember which numbers are in as key, and number reps as value
however, the value caps at 2
then we get the values in the map and add it up

From k we know starting at which index we can stash the extra at

since the judge matches expected[i] === mySolution[i],
this means that the end result array have to be sorted as well

I wonder if I can just put everything before k and resort again
*/
``````

Let me know anything on your mind after reading through this, THANKS!