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

easy array

Problem

Given a binary array nums and an integer k, return true if all 1's are at least k places away from each other (i.e., there are at least k zeros between every two consecutive 1's); otherwise false.

Inputnums = [1,0,0,1,0,1], k = 2

Outputfalse

1's sit at indices 0, 3, 5. The gap 0→3 has 2 zeros (≥ k), but the gap 3→5 has only 1 zero (< k = 2), so the answer is false.

nums (0/1 comma-separated)

def k_length_apart(nums, k):
    prev = -1
    for i, v in enumerate(nums):
        if v == 1:
            if prev != -1 and i - prev - 1 < k:
                return False
            prev = i
    return True

function kLengthApart(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;
}

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;
    }
}

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

Explanation

We only care about the gaps between consecutive 1's, so the simplest approach is to remember the position of the previous 1 and measure the distance each time we hit a new one.

We keep a variable prev for the index of the last seen 1, starting at -1 to signal that none has appeared yet. As we scan, whenever we find a 1, we count the zeros between it and the previous 1 as i - prev - 1.

If that gap is smaller than k (and a previous 1 exists), the rule is violated and we immediately return false. Otherwise we update prev = i and keep going. The very first 1 has nothing to compare against, which is why the prev != -1 guard matters.

Example: nums = [1, 0, 0, 1, 0, 1], k = 2. The 1's sit at indices 0, 3, 5. Gap 0→3 has 3 - 0 - 1 = 2 zeros (ok), but gap 3→5 has 5 - 3 - 1 = 1 zero, which is below k, so the answer is false.

Time: O(n) Space: O(1)