Code Implementation

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

class Solution {
public:
    bool kLengthApart(vector<int>& nums, int k) {
        int prev = -1;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == 1) {
                if (prev != -1 && i - prev - 1 < k) {
                    return false;
                }
                prev = i;
            }
        }
        return true;
    }
};
      

class Solution {
    public boolean kLengthApart(int[] nums, int k) {
        int prev = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                if (prev != -1 && i - prev - 1 < k) {
                    return false;
                }
                prev = i;
            }
        }
        return true;
    }
}
      

var kLengthApart = function(nums, k) {
    let prev = -1;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === 1) {
            if (prev !== -1 && i - prev - 1 < k) {
                return false;
            }
            prev = i;
        }
    }
    return true;
};
      

Problem Description

You are given a binary array nums (an array consisting only of 0s and 1s), and an integer k. Your task is to determine whether all the 1's in nums are at least k places away from each other. In other words, for every pair of 1's in the array, there must be at least k zeros between them.

• nums is a list of integers (only 0 or 1).
• k is a non-negative integer.
• Return True if the condition is satisfied for all 1's, otherwise return False.
• The solution should check all pairs of 1's and ensure the distance between them is at least k.

Thought Process

Let's break down the problem logically. We need to check the distance between every pair of 1's in the array. If every pair of 1's has at least k zeros between them, we return True; otherwise, we return False.

The brute-force way would be to check every possible pair of 1's, compute their distance, and see if it's at least k. However, this is inefficient. A better idea is to walk through the array once, keep track of the position of the previous 1, and when we find a new 1, check if the gap (number of zeros) between the current and previous 1 is at least k.

This approach is efficient because it avoids unnecessary comparisons and works in a single pass through the array.

Solution Approach

• Step 1: Initialize a variable (let's call it prev) to keep track of the index of the last seen 1. Set it to -1 initially, indicating that we haven't seen any 1 yet.
• Step 2: Iterate through the array using a loop, with both the index and the value at each position.
• Step 3: When you encounter a 1:
  • If prev is not -1, compute the number of zeros between this 1 and the previous 1: i - prev - 1.
  • If this number is less than k, return False immediately (the requirement is violated).
  • Otherwise, update prev to the current index.
• Step 4: If the loop finishes without returning False, return True.

This approach only needs a single variable and a single pass, making it simple and efficient. We use a variable instead of a data structure like a list or map because we only care about the most recent 1.

Example Walkthrough

Let's walk through an example with nums = [1,0,0,0,1,0,0,1] and k = 2.

1. Start with prev = -1.
2. At index 0: nums[0] = 1. Since prev = -1, set prev = 0.
3. Indexes 1, 2, 3: nums is 0, so do nothing.
4. At index 4: nums[4] = 1. The gap is 4 - 0 - 1 = 3, which is >= k. Set prev = 4.
5. Indexes 5, 6: nums is 0, do nothing.
6. At index 7: nums[7] = 1. The gap is 7 - 4 - 1 = 2, which is equal to k. Set prev = 7.
7. No more elements. Since all gaps are at least k, we return True.

If, for example, nums = [1,0,1] and k = 1, the gap is 2 - 0 - 1 = 1, which is not less than k, so we return True. But if k = 2, the gap is less than k, so we return False.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(n²), where n is the number of elements in nums, because you would check every pair of 1's.
  • Space Complexity: O(1), if you just use indices and counters.
• Optimized approach (as implemented above):
  • Time Complexity: O(n), because you scan the array once.
  • Space Complexity: O(1), since only a single integer variable is used.

The optimized solution is both time and space efficient.

Summary

The key insight is that you only need to compare the positions of consecutive 1's in the array to check if they are at least k apart. By keeping track of the previous 1's index and checking the distance each time you encounter a new 1, you can solve the problem in a single pass with constant space. This makes the solution both elegant and efficient, avoiding unnecessary comparisons and extra memory use.