Check If All 1s Are at Least Length K Places Away: Linear Scan Pattern
You are given a binary array nums and an integer k. Return true if every pair of 1s in the array is separated by at least k zeros. If there are fewer than two 1s in the array, return true automatically.
This is LeetCode 1437: Check If All 1's Are at Least Length K Places Away, an easy problem that teaches you how to track the position of the last occurrence of a value during a linear scan.
Why this problem matters
This problem is a clean example of the "last seen index" pattern. Instead of comparing every pair of 1s (which would be O(n^2)), you keep a single variable that records where you last saw a 1. Each time you find another 1, you compare its index to the stored position and check whether the gap is large enough. One variable, one pass, done.
You will see this same pattern in problems that ask about minimum distance between elements, detecting duplicates within a window, or validating spacing constraints. Once the "track the last index" idea clicks, you can apply it to many variations without rethinking from scratch.
The approach
Walk through nums from left to right. Maintain a variable prev that stores the index of the most recent 1 you have seen. Initialize it to -1 (meaning you have not seen any 1 yet).
At each index i:
- If
nums[i] == 1andprev != -1, compute the gap:i - prev - 1. If the gap is less thank, returnfalseimmediately. - If
nums[i] == 1, updateprev = i.
If you finish the scan without returning false, return true.
def kLengthApart(nums, k):
prev = -1
for i in range(len(nums)):
if nums[i] == 1:
if prev != -1 and i - prev - 1 < k:
return False
prev = i
return True
The gap formula i - prev - 1 counts only the zeros between the two 1s. For example, if the previous 1 is at index 0 and the current 1 is at index 4, the gap is 4 - 0 - 1 = 3, which means there are 3 zeros separating them.
The key insight is that you only need to check consecutive pairs of 1s. If every consecutive pair satisfies the distance constraint, then every non-consecutive pair automatically satisfies it too, since non-consecutive pairs are farther apart.
Step-by-step walkthrough
Let's trace through nums = [1, 0, 0, 0, 1, 0, 0, 1] with k = 2.
Step 1: Start scanning, k = 2
nums[0] = 1. No previous 1 exists yet. Record prev = 0.
Step 2: Check indices 1, 2, 3 (all zeros)
nums[1], nums[2], nums[3] are all 0. Nothing to check. Keep scanning.
Step 3: Found 1 at index 4, check distance
nums[4] = 1. Distance from prev (index 0): 4 - 0 - 1 = 3. Since 3 >= k (2), this is valid. Update prev = 4.
Step 4: Check indices 5, 6 (zeros)
nums[5] and nums[6] are 0. Skip them.
Step 5: Found 1 at index 7, check distance
nums[7] = 1. Distance from prev (index 4): 7 - 4 - 1 = 2. Since 2 >= k (2), this is valid. Update prev = 7.
Step 6: Scan complete, return true
All pairs of 1s are at least k = 2 places apart. Return true.
Every time we hit a 1, we measure the gap from the previous 1. Both gaps (3 and 2) are at least k = 2, so the answer is true.
Complexity analysis
| Metric | Value |
|---|---|
| Time | O(n), single pass through the array |
| Space | O(1), only one extra variable prev |
The early return on failure means we might stop before scanning the entire array, but worst case we visit every element exactly once.
The building blocks
This problem is built on two reusable ideas that appear in many array problems.
1. Tracking the last seen index
Instead of storing all positions of a target value and comparing them pairwise, you keep a single variable that records the most recent position. This reduces space from O(count) to O(1) and avoids nested loops.
prev = -1
for i in range(len(nums)):
if nums[i] == 1:
if prev != -1:
gap = i - prev - 1
prev = i
This pattern appears whenever you need to compute distances or gaps between occurrences of a specific value in a sequence.
2. Early termination on constraint violation
When validating a constraint across the entire array, you can return false as soon as you find a single violation. There is no need to continue scanning. This is a small optimization but it makes the intent of the code clear: you are checking a universal property.
if prev != -1 and i - prev - 1 < k:
return False
This early exit pattern shows up in validation problems, sorted-order checks, and monotonicity tests.
Edge cases to watch for
- No 1s at all
nums = [0, 0, 0], k = 1:prevstays at -1, no comparison ever happens. Return true. - Single 1
nums = [0, 1, 0], k = 5: only one 1 means no pair to compare. Return true. - Adjacent 1s
nums = [1, 1, 0], k = 1: gap is1 - 0 - 1 = 0, which is less thank = 1. Return false. - k is 0
nums = [1, 1, 1], k = 0: every gap of 0 satisfiesgap >= 0. Return true. - 1s at the boundaries
nums = [1, 0, 1], k = 1: gap is2 - 0 - 1 = 1, which equalsk. Return true (the condition is "at least k", so equality passes).
From understanding to recall
This problem is simple to understand once you see the trick: track the previous 1 and compare gaps. But simplicity in understanding does not always mean you will reproduce it quickly under pressure. The gap formula i - prev - 1 and the initialization of prev = -1 are small details that trip people up when they are writing code on a whiteboard.
Spaced repetition helps you lock in these details. After a few review sessions spaced over days and weeks, you will not need to re-derive the formula or wonder about the initial value. You will just know it, the same way you know that len() gives you the length of a list.
Related posts
- Max Consecutive Ones III - Another binary array problem with distance and window constraints
- Move Zeroes - In-place array manipulation with a tracking pointer
- Can Place Flowers - Greedy spacing validation in an array
Practice builds permanence. Each of these problems reinforces the linear scan pattern in a slightly different way, helping you generalize the technique rather than memorizing individual solutions.