Check If All 1's Are at Least Length K Places Away - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

EasyArray15 min readAsked at: Meta, Google, Bloomberg

Practice this problem

Problem Statement

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 <= 10⁵
0 <= k <= nums.length
nums[i] is 0 or 1

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.

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.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n), where n is the number of elements in nums.

Space Complexity: O(1), as only a few variables are used.

Try this approach in the editor →

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.

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.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n), with n being the size of nums array.

Space Complexity: O(1), utilizing constant space to track count.

Try this approach in the editor →

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).

Code

Python Java C++Go TypeScript Rust

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

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	—

Detailed 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.

Video Solution

Check If All 1's Are at Least Length K Places Away | Easy | Leetcode 1437 | codestorywithMIK • codestorywithMIK • 2,944 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Check If All 1's Are at Least Length K Places Away with our built-in code editor and test cases.

Practice on FleetCode

Task Scheduler II

Problem Info

DifficultyEasy

Acceptance64.3%

Approaches3

Reading time15 min

Asked at

Meta Google Bloomberg

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Simple Linear Scan

Code

Complexity

Approach 2: Calculating Gaps Between 1s

Code

Complexity

Approach 3: Simulation

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents