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

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

What is this problem about?

The "Check If All 1's Are at Least Length K Places Away interview question" is an array distance validation task. You are given a binary array (containing only 0s and 1s) and an integer k. You need to determine if every pair of '1's in the array are separated by at least k zeros. In other words, the distance between the indices of any two 1s must be at least $k+1$.

Why is this asked in interviews?

Meta and Bloomberg ask the "Check If All 1's Are at Least Length K Places Away coding problem" to evaluate a candidate's ability to maintain state while traversing an array. It tests your logic in tracking the "last seen" position of a specific element and your ability to implement an $O(N)$ solution with minimal space. It’s a fundamental "Array interview pattern" problem.

Algorithmic pattern used

This problem uses the Linear Scan with State Tracking pattern.

1. Initialize: Keep a variable last_pos to store the index of the most recently encountered '1'. Initialize it to a value that won't trigger a failure (like -1 or a very small negative number).
2. Iterate: Loop through the array from index 0 to $n-1$.
3. Condition: When you encounter a '1':
   • If last_pos is not -1, check the distance: current_index - last_pos - 1.
   • If this distance is less than k, return false.
   • Update last_pos to the current index.
4. Success: If you finish the loop without any violations, return true.

Example explanation

Array: [1, 0, 0, 0, 1, 0, 1], $k = 2$

1. index 0: It's a '1'. last_pos = 0.
2. index 4: It's a '1'. Distance: $4 - 0 - 1 = 3$. $3 \geq 2$. OK. last_pos = 4.
3. index 6: It's a '1'. Distance: $6 - 4 - 1 = 1$. $1 < 2$. FAIL! Result: False.

Common mistakes candidates make

• Off-by-one errors: Calculating the distance incorrectly (e.g., using current - last instead of current - last - 1).
• Initial State: Not handling the first '1' correctly, causing the distance check to run when it shouldn't.
• Nested Loops: Using a nested loop to look ahead for the next '1', which is $O(N^2)$ in the worst case. A single pass is $O(N)$.

Interview preparation tip

Always look for ways to solve array distance problems in a single pass. Keeping track of the "previous occurrence" index is a classic trick that appears in many variations of this "Array interview pattern."