Leetcode diary: Remove Duplicates from Sorted Array II

LINK

Worst day. Was stuck on this problem for 2+ hours then 1+ today after sleeping on it :( ....

Something just didn't click with me on this problem so I'll write it down for my sake, hope it'll help you too!

the easy version of this question is actually easy with a twist so we'll start from there:

how do we in-place reassign values in an sorted array such that the first K elements of the array are all unique. Anything after K is ignored.

Being sorted is important because then all the same numbers are in a row so you CAN do something better than using a set/hashmap.

the in-place part just make this question hard enough to be easy-level leetcode.

To solve this problem, you'll need two concept:

1.) An index that points at the actual index of the array that you'll return (the k value)

2.) Swap function that doesn't swap values of two indexes, but rather just swap in the value from one index to the other. This is critical because if you do a regular i<->j index swap, you'll end up having to deal with having to persistently skip the swapped-backward index

you can do this question looking forward or looking backward of the current index, I elected backward. Here is the pseudo code

1.) init kIndex=1, currentIndex
2.) for loop on currentIndex and inputArray
3.) if the nums[currentIndex] !== nums[currentIndex-1], swap(inputArray, kIndex, currentIndex); kIndex++; 
4.) else skip 
5.) return kIndex

kIndex=1 part is a bit tricky, but remember that k is both "the number of elements in inPutArray that contains unique values after function run" and "index where you would swap"

It is impossible for the "number of unique elements" to be 0 and it's also impossible for "index to swap" to be 0 (since 0-index value should always be the unique one anyways).

you'll have to get into a habit of understanding the question and initialize accordingly to the question. Cant always just start at 0. I see there are some solution that start at 0, but then in the end they'd need to return k+1, so you'll have to adjust one way or another.

4th step, else skip, is also the tricky part. you skip because you only want to increment the currentIndex value and not the kIndex. This way you are programming the behavior "increment until we find the next unique value in the array"

For 3rd step, you are programming "I found a new unique number and I made sure it's pushed to the front of the array, then made sure we know where the next possible unique number index should be"

Now let's start doing the question we were here for :) ...
the second version is exactly the same, but each number can have 2 copies in the final array now instead of 1 only.

test cases (always start with these in an interview, get in a habit now):
[1,2,3,4,5] -> no change
[1,1,2,3,4,5] -> no change
[1,1,1,2,3,4,5] -> [1,1,2,3,4,5]
[1,1,1,2,2,3,4,5] -> [1,1,2,2,3,4,5]
[1,1,1,2,2,2,3,4,5] -> [1,1,2,2,2,3,4,5]
[1,1,1,2,2,2,3,4,5,5] -> [1,1,2,2,2,3,4,5,5]
[1,1,1,2,2,2,3,4,5,5,5] -> [1,1,2,2,2,3,4,5,5]

the first thing that should come in mind is that
well who's the source of truth? who knows which numbers that are actually duplicated as we loop through the array and do all the swapping, skipping, and incrementing the indexes?

the answer is that the kIndex actually holds the value and of course now we need its side kick: kIndexMinus1 so that we know whether the number has already showed twice and we need to skip until the next unique number.

why kIndex? because we are always swapping into the kIndex position, so as the code handles different usecases, it's always the kIndex that keeps track of what's going on.

With this in mind, we should go back to the easy-level question again, sorry just one last time, and update our code so that we can practice coding "the kIndex holds the source of truth"

function swapInOnly (nums, swapInIndex, swappedFromIndex) {
    if (swapInIndex === swappedFromIndex) return
    nums[swapInIndex] = nums[swappedFromIndex]
}

function removeDuplicates (nums) {
    let kIndex = 0
    for (let index=1; index<nums.length; index++) {
        const num = nums[index]
       if (num !== nums[kIndex]) {
            swapInOnly(nums, kIndex+1, index)
            kIndex++
        }
    }
    return kIndex+1
}

okay so the interesting part and difficult part is actually over. This is made simple because we choose to use kIndex as the truth holder on what is the current state of the array. Feel free to scroll down to my attempts when I did not do that.

we would now:
1.) initialize kIndex=2
2.) start looping with currentIndex=2
3.) at each iteration init variables for
const num = nums[currentIndex]
const oneBefore = nums[kIndex-1]
const twoBefore = nums[kIndex-2]
4.) if num === oneBefore === twoBefore, do nothing and continue loop
5.) else swap currentIndex and kIndex, kIndex++

That's it!
the solution is very simple because we use kIndex as source of truth on what is the current state of the array, does the array have 2 or less copies of each unique number?

You can think of this as a stack question where we are adding to the stack IF less than 2 copies of the number in the array.

Full code below with extra handling on an edge case

function swapInOnly (nums, swapInIndex, swappedFromIndex) {
    if (swapInIndex === swappedFromIndex) return
    nums[swapInIndex] = nums[swappedFromIndex]
}

function removeDuplicates (nums) {
    if (nums.length < 3) return nums.length
    let kIndex = 2
    let oneBefore
    let twoBefore

    for (var i=2; i < nums.length; i++) {
        const number = nums[i]
        oneBefore = nums[kIndex-1]
        twoBefore = nums[kIndex-2]

        if (number === oneBefore && number === twoBefore) {
            continue
            //or you can write the code so it doesn't need this do nothing block, but I think the logic is a little counter-intuitive.
        } 


        if (i=== nums.length-1 && nums[i] === oneBefore && nums[i] === twoBefore) {
            continue
        } 

        swapInOnly (nums, kIndex, i)
        kIndex++
    }
    return kIndex
}

~~ below are my other attempts to NOT use kIndex as truth-holder ~~

okay so why is this important? why can't we just look back to two indexes from currentIndex and see what's up?
this is because you'll have to complicate the kIndex incrementing logic unnecessarily...and probably just get it wrong
consider this example:
[1,1,1,2,2,3,4]
when we get to this place [1,1,1,2,2,3,4]
we should increment currentIndex until the next number
(and do nothing with kIndex === 2, which stays at the bolded index too)
next: [1,1,1,2,2,3,4]
this is when we do the swapping to: [1,1,2,2,2,3,4], kIndex=3
next: [1,1,2,2,2,3,4]
notice that because of the swapIn that was done, the ex-second-2, the bolded one, is now a third occurrence of 2, what should we do?
leave kIndex until we get to integer 3?
we can't, because remember kIndex = 3?
this means we'd get back [1,1,2,3,2,3,4]

we could say that when nums[i] === nums[i-1] === nums[i-2]
we make kIndex = i and continue
however consider: [1,1,1,1,1,1,1,1,1,2,2,2,2,2,3,4]
if we do this, we'll do a first swap at
[1,1,2,1,1,1,1,1,1,2,2,2,2,2,3,4]
then the next one
[1,1,2,2,1,1,1,1,1,2,2,2,2,2,3,4]
however when the next one comes
[1,1,2,2,1,1,1,1,1,2,2,2,2,2,3,4]
we have 3 twos so the code would make kIndex to the bolded index.