Description
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 <= 1050 <= k <= nums.lengthnums[i]is0or1
Solutions
Solution 1: Simulation
We can iterate through the array nums and use a variable j to record the index of the previous 1. When the element at the current position i is 1, we just need to check if i - j - 1 is less than k. If it is less than k, it means there exists a pair of 1s with fewer than k zeros between them, so we return false. Otherwise, we update j to i and continue iterating through the array.
After the iteration is complete, we return true.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
PythonJavaC++GoTypeScriptRust
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(code-box)
