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

The problem asks us to check whether all 1s in a given binary array nums are separated by at least k positions. In other

leetcodeeasyarray

LeetCode Problem 1437

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

The problem asks us to check whether all 1s in a given binary array nums are separated by at least k positions. In other words, for any two indices i and j where nums[i] == nums[j] == 1 and i < j, the difference j - i should be at least k + 1. The input consists of a binary array nums where each element is either 0 or 1, and an integer k which represents the minimum required distance between any two 1s. The expected output is a boolean value: true if the condition is satisfied for all 1s in the array, or false if there is at least one pair of 1s that is too close.

The constraints indicate that the array can be quite large, up to 100,000 elements, so an efficient linear-time solution is needed. Edge cases to consider include arrays with no 1s, arrays where all elements are 1s, and situations where k is zero, meaning there is no distance restriction.

Approaches

The brute-force approach would involve checking the distance between every pair of 1s in the array. For each 1 at index i, we would scan the rest of the array to find other 1s and calculate the distance j - i. This approach works correctly but has a time complexity of O(n²) in the worst case, which is inefficient for large arrays.

The optimal approach leverages a single linear scan. We maintain the index of the last seen 1 and, for each new 1, we calculate the distance to the previous one. If this distance is less than or equal to k, we immediately return false. Otherwise, we continue scanning. This approach works in O(n) time and uses O(1) additional space.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Check all pairs of 1s, inefficient for large arrays
Optimal O(n) O(1) Single scan, track last index of 1, immediately return if distance < k

Algorithm Walkthrough

  1. Initialize a variable lastOne to store the index of the last seen 1. Start with a value of -1 to indicate that no 1 has been seen yet.
  2. Iterate through the array nums with an index i from 0 to len(nums) - 1.
  3. Whenever nums[i] == 1, check if lastOne is not -1.
  4. If lastOne is not -1, calculate the distance i - lastOne. If this distance is less than or equal to k, return false immediately because the condition is violated.
  5. Update lastOne to i to mark the most recent 1.
  6. Continue until the end of the array. If no violations are found, return true.

Why it works: This algorithm ensures that every consecutive pair of 1s is checked exactly once. Since we only compare the distance to the immediately previous 1, we maintain the invariant that all 1s seen so far are at least k apart. If any pair fails the distance check, the function correctly returns false.

Python Solution

from typing import List

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

The implementation initializes lastOne as -1 to handle the case where no 1 has been encountered yet. The enumerate function is used to iterate through the array while keeping track of the index. For each 1, it checks if the distance to the last 1 is sufficient and updates lastOne. The algorithm returns True only if all pairs of 1s satisfy the distance constraint.

Go Solution

func kLengthApart(nums []int, k int) bool {
    lastOne := -1
    for i, num := range nums {
        if num == 1 {
            if lastOne != -1 && i - lastOne - 1 < k {
                return false
            }
            lastOne = i
        }
    }
    return true
}

The Go implementation mirrors the Python version. The range loop provides both index and value, and we check the distance between consecutive 1s in the same manner. Go slices handle the array indexing efficiently, and lastOne is initialized to -1 to represent no previous 1.

Worked Examples

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

Index Value lastOne Distance Check Result
0 1 -1 - lastOne = 0
1 0 0 - -
2 0 0 - -
3 0 0 - -
4 1 0 4 - 0 - 1 = 3 ok, lastOne = 4
5 0 4 - -
6 0 4 - -
7 1 4 7 - 4 - 1 = 2 ok, lastOne = 7

All checks pass, return true.

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

Index Value lastOne Distance Check Result
0 1 -1 - lastOne = 0
1 0 0 - -
2 0 0 - -
3 1 0 3 - 0 - 1 = 2 ok, lastOne = 3
4 0 3 - -
5 1 3 5 - 3 - 1 = 1 fails, return False

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the array, checking each element once
Space O(1) Only a single variable lastOne is used regardless of input size

Since the algorithm only requires a linear scan and constant space, it is efficient even for the maximum input size of 100,000.

Test Cases

# Example tests
assert Solution().kLengthApart([1,0,0,0,1,0,0,1], 2) == True  # spaced correctly
assert Solution().kLengthApart([1,0,0,1,0,1], 2) == False      # too close
assert Solution().kLengthApart([1,0,0,0,1,0,0,0,1], 3) == True # exact spacing

# Edge tests
assert Solution().kLengthApart([0,0,0,0], 1) == True           # no 1's at all
assert Solution().kLengthApart([1,1,1,1], 0) == True           # k=0 allows consecutive 1's
assert Solution().kLengthApart([1,1,1,1], 1) == False          # k=1 fails consecutive 1's

# Large array tests
assert Solution().kLengthApart([1] + [0]*99999 + [1], 99998) == True
assert Solution().kLengthApart([1] + [0]*99999 + [1], 99999) == False
Test Why
[1,0,0,0,1,0,0,1], k=2 Validates normal spacing
[1,0,0,1,0,1], k=2 Tests failure when 1s are too close
[0,0,0,0], k=1 Handles array with no 1s
[1,1,1,1], k=0 Ensures consecutive 1s are allowed if k=0
Large array Checks performance and correctness at scale

Edge Cases

The first edge case is an array with no 1s. Since there are no 1s, the condition is trivially satisfied, and the function must return true. The implementation handles this by never entering the distance check.

The second edge case is when k is zero. In this scenario, any two consecutive 1s are allowed. Our implementation correctly computes the distance as `i -