Copyright (C) 2025 Marc Abonce Seguin
This document is licensed under CC BY-NC-SA 4.0 (Creative Commons Attribution-NonCommercial-ShareAlike).
This means that if you redistribute a copy or a modified version of this work,
YOU MUST PRESERVE THE COPYRIGHT NOTICE AND LICENSE ABOVE!
In practice this means that this should be helpful for you to study for a coding interview, but if you were to use this in an actual interview, you'd be obligated to disclose that you didn't write it yourself.
Also, there's NO WARRANTY!
You receive an array of buckets that are either empty or have a ball inside. 🗑️🏀
You have to calculate the minimum number of times you'd have to move the balls
to have them all in an alternating pattern, so that you have neither 2 adjacent balls
nor 2 balls separated by more than 1 empty bucket.
The ball pattern may not necessarily fill the entire array.
If there is no solution, return -1.
For example:
[🏀⬜🏀⬜🏀] requires 0 moves to have a valid pattern.
[🏀🏀⬜] requires 1 move to end up with [🏀⬜🏀].
[⬜⬜⬜⬜🏀⬜🏀⬜🏀⬜⬜⬜⬜] requires 0 moves, the empty padding doesn't matter.
[🏀⬜⬜⬜⬜⬜🏀⬜🏀] requires 1 move, from the left-most ball towards the right like [⬜⬜⬜⬜🏀⬜🏀⬜🏀].
[🏀🏀⬜🏀] is impossible, so -1 should be returned.
Notes:
You don't need to actually move the balls, just calculate the minimum number of moves.
Input array may be very large, with up to 100,000 values.
This is solved with a fixed-sized sliding window algorithm.
Once we have the total number of balls in the array, we can know if a solution is impossible if the number of balls is more than half the size of the array, e.g. [🏀🏀⬜🏀] is impossible because there is no way to fit 3 balls in 4 slots in an alternating pattern.
With the total number of balls we can also get the hypothetical ideal pattern that we should be getting at the end. For example, for input [🏀⬜⬜⬜⬜⬜🏀⬜🏀] or any other array with 3 balls, we already know that we're looking for a solution that contains [🏀⬜🏀⬜🏀] as a subarray. We don't know yet where exactly would this subarray be ideally located, for example [🏀⬜🏀⬜🏀⬜⬜⬜⬜], [⬜⬜⬜⬜🏀⬜🏀⬜🏀] and [⬜⬜🏀⬜🏀⬜🏀⬜⬜] all look like valid solutions, but some of these require more balls to be moved than others. We have to figure out which solution requires the minimum amount of moves.
If we overlap this ideal pattern over each slot of the input array, we can compare them and see how many balls are missing to complete the solved pattern over each position.
For example:
With input array [⬜⬜⬜⬜🏀⬜🏀🏀⬜⬜⬜⬜⬜]
the solution should include pattern [🔼️⬜🔼️⬜🔼️] (where each 🔼️ should overlap with a ball)
so we iterate that pattern as a sliding window to get the minimum difference.
⬜⬜⬜⬜🏀⬜🏀🏀⬜⬜⬜⬜⬜
🔼️⬜🔼️⬜🔼️
❌⬜❌⬜✅
diff: 2
⬜⬜⬜⬜🏀⬜🏀🏀⬜⬜⬜⬜⬜
⬜🔼️⬜🔼️⬜🔼️
⬜❌⬜❌⬜❌
diff: 3
⬜⬜⬜⬜🏀⬜🏀🏀⬜⬜⬜⬜⬜
⬜⬜🔼️⬜🔼️⬜🔼️
⬜⬜❌⬜✅⬜✅
diff: 1
⬜⬜⬜⬜🏀⬜🏀🏀⬜⬜⬜⬜⬜
⬜⬜⬜🔼️⬜🔼️⬜🔼️
⬜⬜⬜❌⬜❌⬜✅
diff: 2
⬜⬜⬜⬜🏀⬜🏀🏀⬜⬜⬜⬜⬜
⬜⬜⬜⬜🔼️⬜🔼️⬜🔼️
⬜⬜⬜⬜✅⬜✅⬜❌
diff: 1
⬜⬜⬜⬜🏀⬜🏀🏀⬜⬜⬜⬜⬜
⬜⬜⬜⬜⬜🔼️⬜🔼️⬜🔼️
⬜⬜⬜⬜⬜❌⬜✅⬜❌
diff: 2
⬜⬜⬜⬜🏀⬜🏀🏀⬜⬜⬜⬜⬜
⬜⬜⬜⬜⬜⬜🔼️⬜🔼️⬜🔼️
⬜⬜⬜⬜⬜⬜✅⬜❌⬜❌
diff: 2
⬜⬜⬜⬜🏀⬜🏀🏀⬜⬜⬜⬜⬜
⬜⬜⬜⬜⬜⬜⬜🔼️⬜🔼️⬜🔼️
⬜⬜⬜⬜⬜⬜⬜✅⬜❌⬜❌
diff: 2
⬜⬜⬜⬜🏀⬜🏀🏀⬜⬜⬜⬜⬜
⬜⬜⬜⬜⬜⬜⬜⬜🔼️⬜🔼️⬜🔼️
⬜⬜⬜⬜⬜⬜⬜⬜❌⬜❌⬜❌
diff: 3
Minimum diff is also the minimum number of moves: 1
A simple implementation would use O(m) space,
where m is the number of balls in the array
(or the length of the sliding window, which depends on the number of balls in the array).
This is because of the ideal pattern array that we use as our sliding window.
However, this can be improved to O(1) by removing the auxiliary ideal pattern array, which is technically unnecessary because once we know the number of balls, we can calculate the size of the ideal pattern and it will always have the same sequence.
The above implementation would have a time complexity of
O(n*m) where n is the length of the input array and m is the number of balls in the array.
This is because the sliding window itself iterates the whole array once, but inside each iteration
we count the diff between the ideal pattern and the actual array, which is a linear operation
of the size of the ideal pattern.
Time complexity can be reduced to O(n), or 3 linear loops in total,
by not recalculating values in the nested loop.
The first loop is always needed to count the number of balls in the input array.
Then, instead of passing the sliding window once, one spot at the time,
and recalculating the diff each time, we can iterate twice: once for even-numbered slots only
and then for odd-numbered slots only.
This way, we don't have to compare the entire ideal pattern against the subarray every single time.
Instead, we only have to "forget" the previous left-most slot and compare
the new right-most slot.
For example:
First we slide window over even-numbered indices, starting at index 0
and we calculate diff just like we did before:
⬜⬜⬜⬜🏀⬜🏀🏀⬜⬜🏀⬜⬜🏀⬜
🔼️⬜🔼️⬜🔼️⬜🔼️⬜🔼️
❌⬜❌⬜✅⬜✅⬜❌
diff: 3
Then we skip 2 slots at once.
We "remember" 4 of the previous overlapping values 💡, so we don't need to compare those again.
Instead, we only "forget" the previous left-most difference 🔥
and add the new right-most difference 🔍.
Old diff was 3, the previous left-most slot was different ❌ so we "forget" that difference (-1)
and we add the new right-most difference (+0 because ball was found where ideal pattern expected it ✅).
⬜⬜⬜⬜🏀⬜🏀🏀⬜⬜🏀⬜⬜🏀⬜
⬜⬜🔼️⬜🔼️⬜🔼️⬜🔼️⬜🔼️
🔥⬜💡⬜💡⬜💡⬜💡⬜🔍
⬜⬜❌⬜✅⬜✅⬜❌⬜✅
diff: 3 - 1 + 0 = 2
Same process as above.
Old diff was 2, the previous left-most slot was different ❌ so we "forget" that difference (-1)
and we add the new right-most difference (+1 because ball was not found where ideal pattern expected it ❌).
⬜⬜⬜⬜🏀⬜🏀🏀⬜⬜🏀⬜⬜🏀⬜
⬜⬜⬜⬜🔼️⬜🔼️⬜🔼️⬜🔼️⬜🔼️
⬜⬜🔥⬜💡⬜💡⬜💡⬜💡⬜🔍
⬜⬜⬜⬜✅⬜✅⬜❌⬜✅⬜❌
diff: 2 - 1 + 1 = 2
Old diff was 2, the previous left-most slot matched the ideal pattern ✅, so no difference to be "forgotten" (-0)
and we add the new right-most difference (+1 because ball was not found where ideal pattern expected it ❌).
⬜⬜⬜⬜🏀⬜🏀🏀⬜⬜🏀⬜⬜🏀⬜
⬜⬜⬜⬜⬜⬜🔼️⬜🔼️⬜🔼️⬜🔼️⬜🔼️
⬜⬜⬜⬜🔥⬜💡⬜💡⬜💡⬜💡⬜🔍
⬜⬜⬜⬜⬜⬜✅⬜❌⬜✅⬜❌⬜❌
diff: 2 - 0 + 1 = 3
Then, we would have to repeat the same process by sliding the window through the odd-numbered indices, starting at index 1 and skipping 2 slots at once.
🏀⬜
Min moves: 0
⬜🏀
Min moves: 0
🏀⬜🏀
Min moves: 0
⬜🏀⬜
Min moves: 0
🏀⬜🏀⬜🏀
Min moves: 0
⬜⬜⬜⬜🏀⬜🏀⬜🏀⬜⬜⬜⬜
Min moves: 0
🏀🏀⬜
Min moves: 1
⬜⬜⬜⬜🏀⬜🏀🏀⬜⬜⬜⬜⬜
Min moves: 1
🏀⬜🏀⬜⬜⬜⬜⬜⬜⬜🏀⬜🏀
Min moves: 2
⬜⬜⬜⬜🏀⬜🏀⬜⬜⬜⬜🏀⬜🏀⬜🏀⬜🏀🏀⬜⬜⬜⬜🏀⬜🏀⬜
Min moves: 3
⬜🏀⬜🏀⬜🏀⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜🏀⬜🏀⬜🏀⬜🏀
Min moves: 3
⬜🏀⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜🏀⬜🏀⬜🏀⬜🏀⬜
Min moves: 1
🏀🏀⬜🏀⬜🏀🏀🏀⬜⬜⬜
Min moves: 4
🏀🏀⬜🏀
Min moves: -1
🏀⬜⬜⬜⬜⬜⬜⬜⬜🏀... (i.e. that entire sequence repeated 10,000 times)
Min moves: 16000