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

Easy

#1329Time: 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.

Data structures

Array

Prompt

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:

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:

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 <= 10⁵
0 <= k <= nums.length
nums[i] is 0 or 1

Approaches

2 approaches with complexity analysis and trade-offs.

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 1s meets the requirement.

Algorithm

Create an empty list, oneIndices, to store the indices of all 1s.
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.
After populating the list, check its size. If oneIndices contains fewer than two elements (i.e., zero or one 1s in the array), the condition is trivially satisfied, so return true.
Iterate through the oneIndices list starting from the second element (index p = 1 to oneIndices.size() - 1).
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.
If this calculated gap is less than k, it means two 1s are too close. Return false immediately.
If the loop completes without finding any violations, it means all consecutive 1s are at least k places away. Return true.

Walkthrough

The core idea is to first identify the locations of all the 1s. By storing their indices in a separate list, we can easily calculate the distance between any two consecutive 1s. The distance between two 1s at indices i and j (with i < j) is the number of 0s 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 1s, there are no pairs to check, so the condition is automatically met.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public boolean kLengthApart(int[] nums, int k) {6        List<Integer> oneIndices = new ArrayList<>();7        for (int i = 0; i < nums.length; i++) {8            if (nums[i] == 1) {9                oneIndices.add(i);10            }11        }12 13        if (oneIndices.size() <= 1) {14            return true;15        }16 17        for (int i = 1; i < oneIndices.size(); i++) {18            int prevIndex = oneIndices.get(i - 1);19            int currentIndex = oneIndices.get(i);20            int distance = currentIndex - prevIndex - 1;21            if (distance < k) {22                return false;23            }24        }25 26        return true;27    }28}

Complexity

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.

Trade-offs

Pros

The logic is straightforward and easy to reason about.
It cleanly separates the task of finding the 1s from the task of checking their distances.

Cons

Requires extra space proportional to the number of 1s in the array.
In the worst-case scenario (an array with many 1s), 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).

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.

Algorithm

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.
Iterate through the nums array from left to right.
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.
If the loop completes without returning false, it means all 1s in the array are separated by at least k zeros. Return true.

Walkthrough

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 1s.

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.

1class Solution {2    public boolean kLengthApart(int[] nums, int k) {3        // Initialize count to k to handle the first '1'.4        // This pretends there are k zeros before the array starts.5        int zeroCount = k;6 7        for (int num : nums) {8            if (num == 1) {9                if (zeroCount < k) {10                    return false;11                }12                // Reset the counter after finding a '1'.13                zeroCount = 0;14            } else {15                // Increment the counter for each '0'.16                zeroCount++;17            }18        }19 20        return true;21    }22}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  boolean kLengthApart(int[] nums, int k) {4    int j = -(k + 1);5    for (int i = 0; i < nums.length; ++i) {6      if (nums[i] == 1) {7        if (i - j - 1 < k) {8          return false;9        }10        j = i;11      }12    }13    return true;14  }15}

1class Solution:2    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

1class Solution {2public:3  bool kLengthApart(vector<int> &nums, int k) {4    int j = -(k + 1);5    for (int i = 0; i < nums.size(); ++i) {6      if (nums[i] == 1) {7        if (i - j - 1 < k) {8          return false;9        }10        j = i;11      }12    }13    return true;14  }15};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem