Check If All 1's Are at Least Length K Places Away solution and explanation
Google
9 more videos on this problem
Check If All 1's Are at Least Length K Places Away | Easy | Leetcode 1437 | codestorywithMIKcodestorywithMIK · 7:32 · 2K views
Check If All 1's Are at Least Length K Places Away - Leetcode 1437 - PythonNeetCodeIO · 4:09 · 2K views
Check If All 1's Are at Least Length K Places Away | Live Coding with Explanation | Leetcode #1437Algorithms Made Easy · 5:20 · 849 views
1437 check if all 1's are at least k place away leetcode problem in c++ | leetcode for beginnersCoding enthusiast · 4:59 · 741 views
Check If All 1's Are at Least Length K Places Away | Leet code 1437 | Theory + Python + JavaSai Anish Malla · 10:48 · 371 views
Check If All 1's Are at Least Length K Places Away | LeetCode 1437 | ArrayNaresh Gupta · 4:45 · 335 views
Check If All 1's Are at Least Length K Places Away | Leetcode 1437Coding Decoded · 6:20 · 218 views
Leetcode - Check If All 1's Are at Least Length K Places Away (Python)Timothy H Chang · 5:09 · 174 views
Check If All 1's Are at Least K Places Away | LeetCode 1437 | Beginner FriendlySanyam IIT Guwahati · 8:37 · 160 views
1437. Check If All 1's Are at Least Length K Places Away (Leetcode Medium)Programming Live with Larry · 2:54 · 107 views
The problem
Given an binary array nums and an integer k, return true if all 1's are at least k places away from each other, otherwise return false.
Example 1:
Input: nums = [1,0,0,0,1,0,0,1], k = 2 Output: true Explanation: Each of the 1s are at least 2 places away from each other.
Example 2:
Input: nums = [1,0,0,1,0,1], k = 2 Output: false Explanation: The second 1 and third 1 are only one apart from each other.
Constraints:
1 <= nums.length <= 1050 <= k <= nums.lengthnums[i]is0or1
Approach overview
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.
Approach 1: Simple Linear Scan
This approach involves iterating through the array and keeping track of the most recent index where a '1' has been encountered. For every '1' encountered, check if the distance from the last '1' is at least 'k'. If any distance is found to be less than 'k', return false. If the loop ends without returning false, return true.
def kLengthApart(nums, k):
lastIndex = -1
for i in range(len(nums)):
if nums[i] == 1:
if lastIndex != -1 and i - lastIndex - 1 < k:
return False
lastIndex = i
return Trueclass Solution {
public boolean kLengthApart(int[] nums, int k) {
int lastIndex = -1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 1) {
if (lastIndex != -1 && i - lastIndex - 1 < k) {
return false;
}
lastIndex = i;
}
}
return true;
}
}#include <vector>
using namespace std;
class Solution {
public:
bool kLengthApart(vector<int>& nums, int k) {
int lastIndex = -1;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == 1) {
if (lastIndex != -1 && i - lastIndex - 1 < k) {
return false;
}
lastIndex = i;
}
}
return true;
}
};function kLengthApart(nums, k) {
let lastIndex = -1;
for (let i = 0; i < nums.length; i++) {
if (nums[i] === 1) {
if (lastIndex !== -1 && i - lastIndex - 1 < k) {
return false;
}
lastIndex = i;
}
}
return true;
}#include <stdbool.h>
bool kLengthApart(int* nums, int numsSize, int k) {
int lastIndex = -1; // mark the last position of 1
for (int i = 0; i < numsSize; i++) {
if (nums[i] == 1) {
if (lastIndex != -1 && i - lastIndex - 1 < k) {
return false;
}
lastIndex = i;
}
}
return true;
}public class Solution {
public bool KLengthApart(int[] nums, int k) {
int lastIndex = -1;
for (int i = 0; i < nums.Length; i++) {
if (nums[i] == 1) {
if (lastIndex != -1 && i - lastIndex - 1 < k) {
return false;
}
lastIndex = i;
}
}
return true;
}
}The Python solution employs a similar logic of iterating the entire array and checking the distances between the indices of the '1's.
Time Complexity: O(n) for iterating through the nums list.
Space Complexity: O(1) because it uses only constant space.
Approach 2: Calculating Gaps Between 1s
This method includes scanning the array to compute gaps between '1's using a counter. If the gap calculated is ever less than k while traversing, return false. This process continues until the scan ends, signifying all gaps are adequate, thus returning true.
def areGapsValid(nums, k):
count = k
for num in nums:
if num == 1:
if count < k:
return False
count = 0
else:
count += 1
return Trueclass Solution {
public boolean areGapsValid(int[] nums, int k) {
int count = k;
for (int num : nums) {
if (num == 1) {
if (count < k) return false;
count = 0;
} else {
count++;
}
}
return true;
}
}#include <vector>
using namespace std;
class Solution {
public:
bool areGapsValid(vector<int>& nums, int k) {
int count = k;
for (int num : nums) {
if (num == 1) {
if (count < k) return false;
count = 0;
} else {
count++;
}
}
return true;
}
};function areGapsValid(nums, k) {
let count = k;
for (let num of nums) {
if (num === 1) {
if (count < k) return false;
count = 0;
} else {
count++;
}
}
return true;
}#include <stdbool.h>
bool areGapsValid(int* nums, int numsSize, int k) {
int count = k; // Initialize with k to prevent false on first 1
for (int i = 0; i < numsSize; i++) {
if (nums[i] == 1) {
if (count < k) return false;
count = 0;
} else {
count++;
}
}
return true;
}public class Solution {
public bool AreGapsValid(int[] nums, int k) {
int count = k;
foreach (var num in nums) {
if (num == 1) {
if (count < k) return false;
count = 0;
} else {
count++;
}
}
return true;
}
}This Python method iterates through nums, counting zeros. It verifies each '1' is correctly distanced from its predecessor by checking the counter upon every '1'.
Time Complexity: O(n), accounting for each list element.
Space Complexity: O(1) with only a counter variable maintained.
Approach 3: Simulation
We can iterate through the array nums and use a variable j to record the index of the previous 1. When the element at the current position i is 1, we just need to check if i - j - 1 is less than k. If it is less than k, it means there exists a pair of 1s with fewer than k zeros between them, so we return false. Otherwise, we update j to i and continue iterating through the array.
After the iteration is complete, we return true.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
function kLengthApart(nums: number[], k: number): boolean {
let j = -(k + 1);
for (let i = 0; i < nums.length; ++i) {
if (nums[i] === 1) {
if (i - j - 1 < k) {
return false;
}
j = i;
}
}
return true;
}func kLengthApart(nums []int, k int) bool {
j := -(k + 1)
for i, x := range nums {
if x == 1 {
if i-j-1 < k {
return false
}
j = i
}
}
return true
}impl Solution {
pub fn k_length_apart(nums: Vec<i32>, k: i32) -> bool {
let mut j = -(k + 1);
for (i, &x) in nums.iter().enumerate() {
if x == 1 {
if (i as i32) - j - 1 < k {
return false;
}
j = i as i32;
}
}
true
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Simple Linear Scan | Time Complexity: O(n) for iterating through the nums list. Space Complexity: O(1) because it uses only constant space. |
| Calculating Gaps Between 1s | Time Complexity: O(n), accounting for each list element. Space Complexity: O(1) with only a counter variable maintained. |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Linear Scan (track last index of 1) | O(n) | O(1) | Best general solution. Clean single pass and early exit when spacing rule breaks. |
| Calculating Gaps Between 1s | O(n) | O(1) | Useful when reasoning directly about zero counts between elements. |
Frequently asked questions
Is Check If All 1's Are at Least Length K Places Away easy or hard?
Check If All 1's Are at Least Length K Places Away is categorized as an Easy problem. The challenge focuses on careful iteration and handling edge cases such as the first occurrence of 1. Most solutions require only a single pass through the array.
Check If All 1's Are at Least Length K Places Away Python/Java solution
In Python or Java, the solution typically loops through the array and tracks the last index where 1 appeared. When another 1 is found, the code checks if the gap between indices is at least k. The implementation is short, runs in O(n) time, and uses constant extra memory.
How to solve Check If All 1's Are at Least Length K Places Away in O(n)?
Iterate through the array while storing the index of the previous 1. When you encounter a new 1, calculate the number of elements between the two indices. If that gap is smaller than k, return false; otherwise update the previous index and continue. This single pass guarantees O(n) time.
What is the best approach for Check If All 1's Are at Least Length K Places Away?
The best approach is a single linear scan that tracks the index of the last seen 1. When another 1 appears, compute the distance between the two indices and ensure it is at least k. This runs in O(n) time with O(1) extra space and exits early if a violation occurs.
Is Check If All 1's Are at Least Length K Places Away asked at Google/Amazon/Meta?
Variants of array spacing and distance validation problems appear in interviews at companies like Amazon, Google, and Meta. They test basic iteration logic, boundary conditions, and the ability to derive constraints from index differences. While the exact problem may vary, the pattern is common in entry-level interview rounds.
What data structure is used in Check If All 1's Are at Least Length K Places Away?
The problem primarily uses an array traversal technique. No additional data structures such as hash maps or stacks are necessary because only the previous index of 1 or a running zero counter needs to be stored.
What is the time complexity of Check If All 1's Are at Least Length K Places Away?
The optimal solution runs in O(n) time because the array is scanned exactly once. Each element is processed with constant work, and no nested loops are required. Space complexity remains O(1) since only a few variables are used to track the previous 1 or gap count.