Check If All 1s Are At Least Length K Places Away - Leetcode Solution

The problem "Check If All 1s Are At Least Length K Places Away" on LeetCode asks us to determine whether or not all the 1s in a binary array are at least K distance apart. The problem statement can be found here: https://leetcode.com/problems/check-if-all-1s-are-at-least-length-k-places-away/

To solve this problem, we can iterate through the array and check the distance between every pair of 1s that we encounter. If we find a pair of 1s that are closer than K distance apart, we can immediately return false, as the condition for the problem has been violated. If we reach the end of the array without finding any pairs closer than K distance apart, we can return true, as the condition has been satisfied for all 1s in the array.

Here is the algorithm in more detail:

1. Initialize a variable, prevOne, to -1, which will store the index of the most recent 1 encountered.
2. Iterate through the array from left to right, checking each element: a. If the current element is 1, and prevOne is not -1 (i.e. we have already encountered at least one 1), check if the distance between them is less than K: i. If the distance is less than K, return false, as the condition has been violated. ii. If the distance is greater than or equal to K, update prevOne to the current index and continue iterating. b. If the current element is 1, and prevOne is -1 (i.e. this is the first 1 encountered), set prevOne to the current index and continue iterating.
3. If we reach the end of the array without finding any pairs of 1s closer than K distance apart, return true.

Here is the Python code implementation of the algorithm:

def kLengthApart(nums, k): prevOne = -1 for i in range(len(nums)): if nums[i] == 1: if prevOne != -1 and i - prevOne - 1 < k: return False prevOne = i return True

This algorithm has a time complexity of O(n), where n is the length of the input array, because we iterate through the array once. The space complexity is O(1), because we only use a constant amount of space to store the index of the most recent 1 encountered.

1