algoadvance

You are given an integer array nums representing a binary array, and an integer k.

Return True if all 1's are at least k places away from each other, otherwise return False.

Example:

Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: True

Input: nums = [1,0,0,1,0,1], k = 2
Output: False

Constraints:

Clarifying Questions

  1. Q: Can the array contain elements other than 0 and 1?
    • A: No, the problem explicitly states that nums is a binary array.
  2. Q: Is the array always non-empty?
    • A: Yes, based on the constraint 1 <= nums.length.
  3. Q: What should the function return if k is 0, i.e., the required spacing is zero?
    • A: The function should return True since no spacing is required between 1s.

Strategy

To solve this problem, we can iterate through the array and keep track of the index of the last encountered 1. For each new 1 we encounter, we check the distance from the previous 1. If the distance is less than k, we return False. If we complete the iteration without finding any 1s that are too close, we return True.

Code

def kLengthApart(nums: list[int], k: int) -> bool:
    last_position = -1  # Initialize to -1 which indicates no 1 has been found yet.
    
    for i in range(len(nums)):
        if nums[i] == 1:
            if last_position != -1 and i - last_position - 1 < k:
                return False
            last_position = i
    
    return True

# Test Cases
print(kLengthApart([1, 0, 0, 0, 1, 0, 0, 1], 2))  # True
print(kLengthApart([1, 0, 0, 1, 0, 1], 2))  # False
print(kLengthApart([1, 1, 1, 1, 1], 0))  # True
print(kLengthApart([0, 1, 0, 0, 0, 1, 0, 0, 1, 0], 2))  # True

Time Complexity

The time complexity of this solution is ( O(n) ) where ( n ) is the length of the nums array. This is because we are iterating through the array once.

The space complexity is ( O(1) ) because we only use a few extra variables regardless of the input size.

Try our interview co-pilot at AlgoAdvance.com