Check If All 1's Are at Least Length K Places Away Solution
Check If All 1's Are at Least Length K Places Away solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Check If All 1's Are at Least Length K Places Away is an easy coding problem on arrays, asked in Amazon and Meta interviews.
- Difficulty: Easy
- Topics: Arrays
- Asked at: Amazon, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a binary array nums and an integer k, return true if every pair of adjacent 1's is separated by at least k zeros.
Example 1
Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: true
Explanation: The gaps hold 3 zeros and 2 zeros, both at least 2.
Example 2
Input: nums = [1,0,0,1,0,1], k = 2
Output: false
Explanation: The last two 1's have only one zero between them.
Example 3
Input: nums = [1,1,1,1,1], k = 0
Output: true
Constraints
1 <= nums.length <= 1000000 <= k <= nums.lengthnums[i] is 0 or 1.
Hints for Check If All 1's Are at Least Length K Places Away
Hint 1
Only consecutive 1's matter — you never need to compare non-adjacent ones.
Hint 2
Remember the index of the previous 1 as you scan.
Hint 3
The number of zeros between index
prevand indexiisi - prev - 1.
How to solve Check If All 1's Are at Least Length K Places Away
Track the position of the most recent 1. When the next 1 arrives, the zeros between them are fully determined by the two indices.
Approach
- Initialise
prev = -1meaning "no 1 seen yet". - For each index
iwherenums[i] == 1: ifprev != -1andi - prev - 1 < k, returnfalse. - Otherwise set
prev = iand continue. - Return
trueif the scan completes.
Why it works
If every adjacent pair is far enough apart then every pair is, since gaps only grow when you skip intervening 1's. So checking adjacent pairs is both necessary and sufficient.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Using
i - previnstead ofi - prev - 1counts one of the endpoints as a zero and lets a too-tight pair through. - The first 1 has no predecessor — comparing against
prev = -1without the guard produces a false negative. k = 0must accept adjacent 1's.
Reference solution
Python
from typing import List
def kLengthApart(nums: List[int], k: int) -> bool:
prev = -1
for i, x in enumerate(nums):
if x == 1:
if prev != -1 and i - prev - 1 < k:
return False
prev = i
return TrueJava
public static boolean kLengthApart(int[] nums, int k) {
int prev = -1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 1) {
if (prev != -1 && i - prev - 1 < k) return false;
prev = i;
}
}
return true;
}C++
bool kLengthApart(vector<int>& nums, int k) {
int prev = -1;
for (int i = 0; i < (int) nums.size(); i++) {
if (nums[i] == 1) {
if (prev != -1 && i - prev - 1 < k) return false;
prev = i;
}
}
return true;
}JavaScript
var kLengthApart = function(nums, k) {
let prev = -1;
for (let i = 0; i < nums.length; i++) {
if (nums[i] === 1) {
if (prev !== -1 && i - prev - 1 < k) return false;
prev = i;
}
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays