#1437

Easy

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

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

Check if all 1's in a binary array are at least k places away from each other.

Problem Statement

You are given a binary array, nums, and an integer k. Your task is to check if all 1's in the array are at least k positions away from each other. Return true if they are, and false if not.

For example, in the array nums = [1,0,0,0,1,0,0,1] with k = 2, the output should be true because each of the 1's are at least two places apart from each other. If nums = [1,0,0,1,0,1] with k = 2, the output should be false because the second and third 1's are only one position apart.

Examples

Example 1

Input: nums = [1,0,0,0,1,0,0,1], k = 2

Output: true

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

The second 1 and third 1 are only one apart from each other.

Constraints

1 <= nums.length <= 105
0 <= k <= nums.length
nums[i] is 0 or 1

Solution Approach

Iterate Through the Array

Start by iterating through the array. For each 1, check if the next 1 is at least k positions away. If any 1's are closer than k places, return false immediately.

Track Index of Last 1

Keep track of the index of the last encountered 1. This allows you to check the distance between consecutive 1's and ensures they are separated by at least k places.

Early Exit on Failure

If at any point, the distance between two consecutive 1's is less than k, exit the loop and return false. This saves unnecessary checks once we know the condition is violated.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used. The most efficient solution requires a single pass through the array, resulting in O(n) time complexity, where n is the length of the array. The space complexity is O(1) since only a few variables are needed for tracking indices, regardless of the input size.

What Interviewers Usually Probe

The candidate correctly identifies an array-driven approach.
The candidate is able to identify and handle early termination to optimize performance.
The candidate does not attempt overly complex solutions when a simpler approach works well.

Common Pitfalls or Variants

Common pitfalls

Not handling the case where there are fewer than two 1's in the array, which should immediately return true.
Assuming the array always has two 1's or more without checking edge cases.
Failing to exit early when the distance condition is violated, leading to unnecessary checks.

Follow-up variants

Change the problem to check for a different minimum distance between 1's.
Allow the array to be a circular buffer where the first and last 1 can be considered neighbors.
Add multiple values for k and return an array of boolean results for each value.

FAQ

What is the approach for solving 'Check If All 1's Are at Least Length K Places Away'?

The best approach is to iterate through the array and check the distance between each pair of consecutive 1's. If any pair is too close, return false.

What is the time complexity for this problem?

The time complexity of the optimal solution is O(n), where n is the length of the array, since we only need to iterate through the array once.

Can the problem be solved in constant space?

Yes, the problem can be solved with O(1) space by simply keeping track of the index of the last 1 encountered during the iteration.

How do I handle edge cases in this problem?

Handle cases where there are fewer than two 1's by returning true immediately, as they are trivially at least k places apart.

What is a variant of the 'Check If All 1's Are at Least Length K Places Away' problem?

One variant could involve making the array circular, where the first and last 1's need to also be at least k places apart.

terminal

Solution

Solution 1: Simulation

We can iterate through the array $\textit{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 $1$s with fewer than $k$ zeros between them, so we return $\text{false}$. Otherwise, we update $j$ to $i$ and continue iterating through the array.

1

2

3

4

5

6

7

8

9

class Solution:
    def kLengthApart(self, nums: List[int], k: int) -> bool:
        j = -inf
        for i, x in enumerate(nums):
            if x:
                if i - j - 1 < k:
                    return False
                j = i
        return True

Continue Practicing

#1436 destination city #1438 longest continuous subarray with absolute diff less than or equal to limit #1439 find the kth smallest sum of a matrix with sorted rows