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.

Description Hints 1 Solution Video 7:32

1437. Check If All 1's Are at Least Length K Places Away

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.

Easy64.3% acceptance3 companies

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

Asked at 3 companies

Google Meta Bloomberg

Topics

Array

Hints open one at a time

Hint 1

Each time you find a number 1, check whether or not it is K or more places away from the next one. If it's not, return false.

7:32

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution