# Check If All 1's Are at Least Length K Places Away
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-if-all-1s-are-at-least-length-k-places-away)
Canonical: https://scaleengineer.com/dsa/problems/check-if-all-1's-are-at-least-length-k-places-away
**Data structures:** Array
---
## Problem
Given an binary array `nums` and an integer `k`, return `true` _if all_ `1`_'s are at least_ `k` _places away from each other, otherwise return_ `false`.

**Example 1:**

![](https://assets.glich.co/dsa/check-if-all-1's-are-at-least-length-k-places-away/image0.png) 

**Input:** nums = [1,0,0,0,1,0,0,1], k = 2
**Output:** true
**Explanation:** Each of the 1s are at least 2 places away from each other.

**Example 2:**

![](https://assets.glich.co/dsa/check-if-all-1's-are-at-least-length-k-places-away/image1.png) 

**Input:** nums = [1,0,0,1,0,1], k = 2
**Output:** false
**Explanation:** 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`

# Approaches
## Store Indices and Check Gaps
This approach involves two main steps. First, we iterate through the entire array to find and store the indices of all occurrences of `1`. Then, we iterate through this list of indices to check if the distance between every pair of consecutive `1`s meets the requirement.
**Time:** O(N), where N is the length of the `nums` array. The first pass to find all `1`s takes O(N) time. The second pass over the list of indices takes O(M) time, where M is the number of `1`s. Since M ≤ N, the total time complexity is dominated by the first pass, resulting in O(N). · **Space:** O(M), where M is the number of `1`s in the array. This is because we store the index of every `1` in a list. In the worst case, where the array consists of many `1`s, the space complexity can be O(N), where N is the length of the array.
**Pros:** The logic is straightforward and easy to reason about.; It cleanly separates the task of finding the `1`s from the task of checking their distances.
**Cons:** Requires extra space proportional to the number of `1`s in the array.; In the worst-case scenario (an array with many `1`s), this can lead to high memory usage, potentially O(N).; Involves two separate passes over the data (one over the original array, one over the list of indices).
### Explanation
The core idea is to first identify the locations of all the `1`s. By storing their indices in a separate list, we can easily calculate the distance between any two consecutive `1`s. The distance between two `1`s at indices `i` and `j` (with `i < j`) is the number of `0`s between them, which is `j - i - 1`.

Once we have the list of indices, say `[idx_1, idx_2, idx_3, ...]`, we just need to check if `idx_2 - idx_1 - 1 >= k`, `idx_3 - idx_2 - 1 >= k`, and so on. If we find any pair that violates this condition, we can immediately conclude the result is `false`. If we check all consecutive pairs and find no violations, the result is `true`. If there are fewer than two `1`s, there are no pairs to check, so the condition is automatically met.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean kLengthApart(int[] nums, int k) {
        List<Integer> oneIndices = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                oneIndices.add(i);
            }
        }

        if (oneIndices.size() <= 1) {
            return true;
        }

        for (int i = 1; i < oneIndices.size(); i++) {
            int prevIndex = oneIndices.get(i - 1);
            int currentIndex = oneIndices.get(i);
            int distance = currentIndex - prevIndex - 1;
            if (distance < k) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
1. Create an empty list, `oneIndices`, to store the indices of all `1`s.
2. Iterate through the input array `nums` from left to right. For each element at index `i`:
   - If `nums[i]` is equal to `1`, add the index `i` to the `oneIndices` list.
3. After populating the list, check its size. If `oneIndices` contains fewer than two elements (i.e., zero or one `1`s in the array), the condition is trivially satisfied, so return `true`.
4. Iterate through the `oneIndices` list starting from the second element (index `p = 1` to `oneIndices.size() - 1`).
5. In each iteration, calculate the number of zeros between the current `1` and the previous `1`. The gap is `oneIndices.get(p) - oneIndices.get(p - 1) - 1`.
6. If this calculated `gap` is less than `k`, it means two `1`s are too close. Return `false` immediately.
7. If the loop completes without finding any violations, it means all consecutive `1`s are at least `k` places away. Return `true`.

## Single Pass with Constant Space
A more optimal solution is to iterate through the array just once, using constant extra space. We can achieve this by keeping a running count of the zeros we've seen since the last `1`. When we encounter a new `1`, we check if this count is sufficient.
**Time:** O(N), where N is the length of the `nums` array. We perform a single pass through the array, making the time complexity linear with respect to the input size. · **Space:** O(1). We only use a single integer variable (`zeroCount`) to keep track of the state, regardless of the size of the input array.
**Pros:** Extremely efficient, with optimal O(N) time and O(1) space complexity.; Processes the array in a single pass, making it suitable for very large inputs or streaming data.; Simple implementation once the core logic is understood.
**Cons:** The logic of initializing the counter to `k` might be slightly less intuitive at first glance compared to tracking the last seen index.
### Explanation
This approach avoids storing all indices by processing the array in a single pass. We use a counter to track the number of zeros between consecutive `1`s. 

A clever trick is to initialize this counter to `k`. This ensures that the very first `1` we find in the array will always pass the check, as if it were preceded by an infinite number of zeros. For any subsequent `1`, we check if the number of zeros counted since the previous `1` is at least `k`. If it's not, we return `false`. If it is, we reset the counter to 0 and continue scanning.

For example, with `nums = [1,0,0,1]`, `k = 2`:
- Initialize `zeroCount = 2`.
- `nums[0]` is `1`: `zeroCount` (2) is not less than `k` (2). OK. Reset `zeroCount = 0`.
- `nums[1]` is `0`: `zeroCount` becomes 1.
- `nums[2]` is `0`: `zeroCount` becomes 2.
- `nums[3]` is `1`: `zeroCount` (2) is not less than `k` (2). OK. Reset `zeroCount = 0`.
- Loop ends. Return `true`.

This method is highly efficient as it only requires one pass and a single variable for storage.

```java
class Solution {
    public boolean kLengthApart(int[] nums, int k) {
        // Initialize count to k to handle the first '1'.
        // This pretends there are k zeros before the array starts.
        int zeroCount = k;

        for (int num : nums) {
            if (num == 1) {
                if (zeroCount < k) {
                    return false;
                }
                // Reset the counter after finding a '1'.
                zeroCount = 0;
            } else {
                // Increment the counter for each '0'.
                zeroCount++;
            }
        }

        return true;
    }
}
```
### Algorithm
1. Initialize an integer variable, `zeroCount`, to `k`. This is a key step that elegantly handles the first `1` encountered in the array, as we can imagine `k` zeros preceding the start of the array.
2. Iterate through the `nums` array from left to right.
3. For each number `num` in the array:
   - If `num` is `1`:
     - Check if `zeroCount` is less than `k`. If it is, this means we have encountered a `1` before seeing at least `k` zeros since the last `1`. This violates the condition, so return `false`.
     - If `zeroCount >= k`, the condition is met for this `1`. Reset `zeroCount` to `0` to begin counting the zeros for the next interval.
   - If `num` is `0`:
     - Simply increment `zeroCount`.
4. If the loop completes without returning `false`, it means all `1`s in the array are separated by at least `k` zeros. Return `true`.

# Solutions
### Java

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

```

### Python

```python
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

```

### CPP

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

```