Leetcode diary: group 1s together trilogy [medium, medium, hard]

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.

1151. Minimum Swaps to Group All 1's Together

2134. Minimum Swaps to Group All 1's Together II

1703. Minimum Adjacent Swaps for K Consecutive Ones

Oh boy...after like 2 full days of kicking and screaming, this baby is finally out of the womb, yes I am the mother. I initially randomly clicked on 1151, finished it, did 2134, thought it was not bad, and figured I could try the "related problem" 1703. MY GOD WAS I WRONG. 1703 was a hard level problem that kicked my ass like there is no tomorrow. Today I am excited to share with you the pains I've went through.

1151. Minimum Swaps to Group All 1's Together:

This question was relatively easy, although I cheated a bit by accidentally seeing the related topic is "sliding window" so the big hint was already given away. The question required you to put all the 1s of the array together with minimal swaps, so naturally the first thing to do in this question is to count how many 1s are there in the array.

 const num1s = data.reduce(function(sum, num){
        if(num === 1) sum++;
        return sum
    },0);

Next, the tricky part here is that we want to find the highest density of 1s in the original array. To find this, we are to assume a window of num1s size and slide it through the array to find which array has the highest number of 1s in it. We do not need to count the number of 1s in each window via the loop like num1s, because for each element added, we can increment number of of 1s or do nothing, and we similarly decrement or nothing on each element removed; a queue data structure. In fact, we don't even need a window array, just a simple counter is good enough:

    let windowNum1s = 0;
    let minNum1sInWindow = 0;

    data.forEach(function(num, index){
        if(num === 1) windowNum1s++;

        if(index === num1s-1) { return minNum1sInWindow = num1s-windowNum1s; }

        if(data[index-num1s] === 1) windowNum1s--;
        minNum1sInWindow = Math.min(minNum1sInWindow, num1s-windowNum1s)
    });

    return minNum1sInWindow;

if(index === num1s-1) { return minNum1sInWindow = num1s-windowNum1s; }

This line is to simply stop the function when initializing the array, it accomplishes the same thing as
data.slice(0, num1s).reduce(count1s,0);
for (let i=num1s; i<data.length; i++) {...}

if(data[index-num1s] === 1) windowNum1s--;
This line is how you "shift" elements out of the window

minNum1sInWindow = Math.min(minNum1sInWindow, num1s-windowNum1s)
it is num1s-windowNum1s here because you are counting the number of 0s to swap out of the array.

If you can understand the above, it's time to move onto 2134!

2134. Minimum Swaps to Group All 1's Together II:

This question is literally the same except with the tiny twist that the tail of the array can be "connected" back to the beginning of the array. So what you'll do is essentially the same, but you'll have to extend the for loop until the index of (data.length + num1s -1). Therefore you'll also have to be careful with the index calculation, if you get this during the interview I am sure the interviewer will be a bit more forgiving on the accuracy on this part, but you still wanna do this carefully. Below is the code:

var minSwaps = function(nums) {
    const num1s = nums.reduce(function(sum, num){
       if(num === 1)  sum++;
        return sum;
    },0);

    let num1sInWindow = 0;
    let minSwaps = 0;

    for (let i=0; i<(nums.length+num1s); i++) {
        const index = i >= nums.length ? i-nums.length : i;
        const number = nums[index];

        if(number === 1) { num1sInWindow++; }

        if(i <= num1s-1 ) { 
            minSwaps = num1s - num1sInWindow;
            continue;
        }

        const headIndex = index - num1s >= 0 ? 
              index - num1s : nums.length + (index - num1s)

        if(nums[headIndex] === 1) { num1sInWindow--; }

        minSwaps = Math.min(minSwaps, num1s-num1sInWindow);
    }

    return minSwaps;
};

Now onto the raid boss!
1703. Minimum Adjacent Swaps for K Consecutive Ones
This question is not to be taken lightly, it is a hard level difficulty question for a good reason. It is the best you spend some time by yourself to work through this first, but I'll walk through the solution line by line as it is very hard to understand it just reading through a bunch of text without some code to anchor your understanding. Here is the video that I am showing the code from. If you still have problems understanding, here is the discussion solution that helped me too.

Below are in python, we start out with these inputs:
nums = [0,0,1,1,1,0,1,1,0,1,0,1,1,1,0,0,0,0,1,0,1];
k=4

pos = [i for i, num in enumerate(nums) if num]
// same code in js:
const pos = nums
.map( (num, index) => num > 0 ? index : -1)
.filter( num => num > -1 );

simply recreating an array containing only the indexes of 1s in the original. it looks like this:
[2, 3, 4, 6, 7, 9, 11, 12, 13, 18, 20]

n=len(pos)
pre_sum = {-1:0}

for i in range(n):
    pre_sum[i] = pre_sum[i-1] + pos[i]

This is the prefix sum technique. What it does is just memoizing the sum at each step from 0 to n. I don't know exactly why the author chose to use a dictionary, but here is the result if it was an array
[2, 5, 9, 15, 22, 31, 42, 54, 67, 85, 105].

Next is the crux of the whole problem, I'll post it first so read through it and digest a bit before reading my explanation:

ans = sys.maxsize 
for i in range(n-k+1):
    mid = i+k // 2;
    left = pre_sum[mid-1] - pre_sum[i-1];
    right = pre_sum[i+k-1] - pre_sum[mid]
    ans = min(ans, right-left + (pos[mid]) if k %2 == 0 else 0)

mid = i+k // 2 is just const mid = i+Math.floor(k/2).

The first thing to keep in mind is that we are still doing a sliding window. The middle of the window is mid, the left bound is left, the right bound is right. Now notice that because of the for loop, we are calculating all windows' value, instead of just finding the one with highest density as the previous two medium level question.

Now you'll probably need to grab a pen and paper to work this out, but I'll try to do this via text:
let's say for array:
[z,a,b,c,d,e,f]
the prefix sum becomes
[
z,
z+a,
z+a+b,
z+a+b+c,
z+a+b+c+d,
z+a+b+c+d+e,
z+a+b+c+d+e+f
]

now we are calculating for the window from a to e, so the mid is c.

left = pre_sum[mid-1] - pre_sum[i-1];
will get us:
left = (z+a+b) - (z) = (a+b)

right = pre_sum[i+k-1] - pre_sum[mid]
will get us:
right = (z+a+b+c+d+e) - (z+a+b+c) = (d+e)

Hopefully now you can easily agree that with the prefix sum, we can get the sum of the window to the left of mid and right of mid by choosing the correct presum index and subtract the correct presum index.

Now first answer why mid? the reason is that the middle index in the array has the minimum swaps grouping toward it. It is a small but significant lemma that probably could be mathematically proven true. If you get this in an interview, hopefully he is nice enough to just tell you, it's ridiculous to be sure of this in an interview setting.

With that in mind, since we are to find the minimal adjacent swaps to group all 1s to mid, we need to add up each 1's swaps away from the middle 1 index. This is achieved via: ans = min(ans, right-left + (pos[mid]) if k %2 == 0 else 0)

"right - left" does not really make sense if we are adding up swaps of left and right. The reason is that the numerical value in left and right does not represent number of swaps, it represents the sum of indexes where these 1s are in the original array. To get say a's number swaps away from c, we have to do c-a. Similar d on the right has d-c swaps away from c. Therefore we get:
(d-c + e-c) + (c-a + c-b) = (d+e) + (-a-b) = (d+e) - (a+b) = right - left.
Honestly how do you get this during an interview XD ... I guess doing a lot of presum problems would help a lot, idk really ...

The (pos[mid]) if k %2 == 0 else 0 is just to balance out the number of c in the equation, since i+Math.floor(k/2) would shift the index to the left on odd numbers.

Finally the last we have to take care of is that ans right now really represents how many swaps is required to put all the 1s to mid, not grouping around mid. To achieve this we have to subtract from ans by the number of elements on left and right.

To get the number, you'll need a small math formula. Note that b needs to occupy 1 index away from c and a needs to occupy 2 indexes away from c. Therefore the total amount to subtract from the left side is 1 + 2. It is symmetrical for the right side, so it is 2(1+2) = 4. Now what if our k is really big ? it means that each side can have 1 + 2 + 3 ... + k/2. 1 + 2 + 3 ... + n has a math formula of :
n(n+1)/2, don't you wish you were having your discrete math notes now...
So both sides equals n(n+1) spaces that needs to be subtracted from ans:

n = (k-1)//2;
ans -= n * (n+1)//2 * 2 + ((n+1) if k % 2 ==0 else 0)

note that the final formula above is a bit unnecessary with the n * (n+1)//2 * 2, I am pretty sure you could just do the n*(n+1) and it'd be fine. The additional subtraction for ((n+1) if k % 2 ==0 else 0) is because in the even array length case, the mid is skewed to the left. So for an array length of 4, the mid is at the 1 index, there is only 0 at the left while 2 and 3 at the right. The n(n+1) only calculates the numbers symmetrical left and right, so we need to subtract n+1 for the additional index on the right.

Thanks for reading, I hope you enjoyed this more than I suffered for this. Cannot believe just explaining this required like 2.5 hours in addition to the time I already invested in understanding this complete bull shit... see you all next time haha ...

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