Problem Description

You are given a binary array nums (containing only 0s and 1s) and an integer k. Your task is to determine whether all the 1s in the array are separated by at least k distance from each other.

In other words, between any two consecutive 1s in the array, there must be at least k zeros. If this condition is satisfied for all pairs of consecutive 1s, return true. Otherwise, return false.

For example:

• If nums = [1,0,0,0,1,0,0,1] and k = 2, the function should return true because:

  • Between the first 1 (index 0) and second 1 (index 4), there are 3 zeros
  • Between the second 1 (index 4) and third 1 (index 7), there are 2 zeros
  • Both gaps have at least k = 2 zeros

• If nums = [1,0,0,1,0,1] and k = 2, the function should return false because:

  • Between the second 1 (index 3) and third 1 (index 5), there is only 1 zero
  • This is less than the required k = 2 zeros

The solution tracks the position of the previous 1 and checks if the distance between consecutive 1s meets the requirement.

Intuition

The key insight is that we only need to track consecutive 1s in the array and check the distance between them. We don't need to store all positions of 1s or look ahead - we can solve this in a single pass.

Think of it this way: as we traverse the array from left to right, whenever we encounter a 1, we need to know where the previous 1 was located. The distance between these two 1s tells us how many elements are between them. Since we want at least k zeros between any two 1s, the actual distance should be at least k + 1 (accounting for the positions of the 1s themselves).

For example, if we have [1, 0, 0, 1], the indices of 1s are 0 and 3. The distance is 3 - 0 = 3, but the number of zeros between them is 3 - 0 - 1 = 2.

This leads to a simple approach:

1. Keep track of the index of the last seen 1
2. When we find a new 1, calculate how many positions are between it and the previous 1
3. If the number of zeros (distance - 1) is less than k, we immediately know the condition is violated
4. Update our "last seen 1" position and continue

We initialize the "last seen 1" position to negative infinity (-inf) to handle the edge case where the first element is a 1. This ensures that the first 1 we encounter won't falsely trigger a violation since i - (-inf) - 1 will always be greater than any finite k.

Solution Approach

The implementation uses a single-pass traversal with a tracking variable to monitor the position of the last encountered 1.

Variables used:

• j: Stores the index of the most recently seen 1, initialized to -inf to handle the first 1 gracefully
• i: Current index while iterating through the array
• x: Current element value at index i

Algorithm steps:

1. Initialize the tracker: Set j = -inf to represent that no 1 has been seen yet. Using negative infinity ensures that when we find the first 1, the distance calculation i - j - 1 will always be large enough to pass the check.

2. Iterate through the array: Use enumerate(nums) to get both the index i and value x of each element.

3. Check each 1: When we encounter a 1 (when x is truthy):

   • Calculate the number of zeros between current position i and previous 1 at position j using the formula: i - j - 1
   • If this distance is less than k, immediately return False as the constraint is violated
   • Update j = i to mark this as the new "last seen 1" position

4. Return result: If we complete the iteration without finding any violation, return True.

Example walkthrough: For nums = [1,0,0,0,1,0,0,1] and k = 2:

• Start with j = -inf
• Index 0: Found 1, distance = 0 - (-inf) - 1 > 2 ✓, update j = 0
• Index 4: Found 1, distance = 4 - 0 - 1 = 3 ≥ 2 ✓, update j = 4
• Index 7: Found 1, distance = 7 - 4 - 1 = 2 ≥ 2 ✓, update j = 7
• Return True

The time complexity is O(n) where n is the length of the array, as we traverse it once. The space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through the solution with nums = [1,0,0,1,0,1] and k = 2:

Initial State:

• j = -inf (no previous 1 seen yet)
• We need at least 2 zeros between any two 1s

Step-by-step traversal:

Index 0: nums[0] = 1

• This is a 1, so we check the distance from the previous 1
• Distance calculation: 0 - (-inf) - 1 = very large number
• This is definitely ≥ 2, so we're good
• Update: j = 0 (mark this 1's position)

Index 1: nums[1] = 0

• This is a 0, so we skip it

Index 2: nums[2] = 0

• This is a 0, so we skip it

Index 3: nums[3] = 1

• This is a 1, so we check the distance from the previous 1 at index 0
• Number of zeros between them: 3 - 0 - 1 = 2
• This equals our requirement k = 2, so we're good
• Update: j = 3 (mark this new 1's position)

Index 4: nums[4] = 0

• This is a 0, so we skip it

Index 5: nums[5] = 1

• This is a 1, so we check the distance from the previous 1 at index 3
• Number of zeros between them: 5 - 3 - 1 = 1
• This is less than our requirement k = 2 (we need at least 2 zeros but only have 1)
• Return False immediately

The algorithm correctly identifies that the last two 1s (at indices 3 and 5) only have 1 zero between them, violating the requirement of having at least 2 zeros between consecutive 1s.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the input array nums. The algorithm iterates through the array exactly once using a single for loop with enumerate(). Each operation inside the loop (checking if x is 1, calculating the distance i - j - 1, comparison with k, and updating j) takes constant time O(1). Therefore, the overall time complexity is linear.

Space Complexity: O(1). The algorithm uses only a constant amount of extra space regardless of the input size. The variables used are:

• j: stores the index of the previous 1 (initialized to negative infinity)
• i: the current index from enumerate
• x: the current value from enumerate

These variables don't grow with the input size, making the space complexity constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Distance Calculation

A common mistake is calculating the distance incorrectly by either including the positions of the 1s themselves or using the wrong formula.

Incorrect approaches:

• Using current_index - last_one_position instead of current_index - last_one_position - 1
• Counting the total elements between 1s including the 1s themselves

Why it's wrong: The problem asks for the number of zeros between consecutive 1s, not the total distance. If 1s are at indices 2 and 5, the positions between them are 3 and 4 (two zeros), not three elements.

Solution: Always use the formula current_index - last_one_position - 1 to get the exact count of elements between two positions.

2. Improper Initialization of the Last Position Tracker

Initializing last_one_position to 0 or -1 instead of negative infinity can cause issues with the first 1 in the array.

Problem scenario:

# Wrong initialization
last_one_position = -1
# If first 1 is at index 0 and k = 2
# Distance = 0 - (-1) - 1 = -1 < 2 (incorrectly fails!)

Solution: Initialize to float('-inf') to ensure the first 1 always passes the distance check, as it has no preceding 1 to compare against.

3. Off-by-One Error in Distance Validation

Some might check distance_between_ones <= k instead of distance_between_ones < k.

Why it matters: The problem requires "at least k" zeros between 1s. If there are exactly k zeros, that satisfies the requirement.

Correct validation:

if distance_between_ones < k:  # Correct: fails only if less than k
    return False

4. Forgetting to Update the Last Position

After checking the distance, failing to update last_one_position = current_index will cause all subsequent distance calculations to be wrong.

Impact: The algorithm would always compare new 1s against the first 1 found, giving incorrect results for arrays with more than two 1s.

Solution: Always update the tracker after validating the distance:

if value == 1:
    if distance_between_ones < k:
        return False
    last_one_position = current_index  # Don't forget this!