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] is 0 or 1Problem 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.
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.
The code defines a function that iterates over the entire array, keeping track of the last index where '1' occurred. If another '1' is found and the distance from the last occurrence is less than k, it returns false. Otherwise, it updates the last index and continues scanning.
Time Complexity: O(n), where n is the number of elements in nums.
Space Complexity: O(1), as only a few variables are used.
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.
The solution checks each element, increasing count when a '0' is found and resetting or checking it when a '1' appears. If count is ever less than k upon seeing '1', false is returned instantly.
Time Complexity: O(n), with n being the size of nums array.
Space Complexity: O(1), utilizing constant space to track count.
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).
| Approach | Complexity |
|---|---|
| Simple Linear Scan | Time Complexity: O(n), where n is the number of elements in nums. Space Complexity: O(1), as only a few variables are used. |
| Calculating Gaps Between 1s | Time Complexity: O(n), with n being the size of nums array. Space Complexity: O(1), utilizing constant space to track count. |
| Simulation | — |
| 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. |
Check If All 1's Are at Least Length K Places Away | Easy | Leetcode 1437 | codestorywithMIK • codestorywithMIK • 2,863 views views
Watch 9 more video solutions →Practice Check If All 1's Are at Least Length K Places Away with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor