Check If All 1's Are at Least Length K Places Away - Video Solutions

Problem Overview: You are given a binary array where 1 represents an occupied slot and 0 represents an empty one. The task is to check whether every pair of 1s is separated by at least k zeros. If any two 1s appear closer than k positions, return false; otherwise return true.

Approach 1: Simple Linear Scan (O(n) time, O(1) space)

Scan the array once while remembering the index of the last seen 1. Every time you encounter another 1, compute the distance from the previous one using currentIndex - lastIndex - 1. If this distance is smaller than k, the constraint is violated and you return false immediately. Otherwise update the last seen position and continue scanning.

This approach relies on a single pass through the array and constant extra memory. The key insight is that you only care about the nearest previous 1, not all earlier ones. Early termination also helps in cases where a violation appears quickly.

Approach 2: Calculating Gaps Between 1s (O(n) time, O(1) space)

Another way is to explicitly count the number of zeros between consecutive 1s. Iterate through the array while maintaining a running counter of zeros since the last 1. When you hit a 1, check whether the zero counter is at least k. If it is smaller and this is not the first 1, the rule fails.

After processing the 1, reset the zero counter and continue. This method focuses directly on gap lengths rather than index differences. Conceptually it behaves like a lightweight sliding distance check across the array, making the spacing constraint explicit and easy to reason about.

Both solutions run in linear time and constant space since the array is processed exactly once and no additional data structures are required. Problems like this appear frequently in interview settings to test careful iteration and edge‑case handling in arrays.

Recommended for interviews: The simple linear scan is the most direct and commonly expected solution. It shows that you can track state while iterating through an array and compute distances efficiently. Explaining the gap-counting variant demonstrates deeper reasoning about the same constraint, but interviewers typically expect the single-pass index tracking approach.