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

Difficulty: Easy | Acceptance: 64.30% | Paid: No Topics: Array

Given an array nums of 0s and 1s and an integer k, return true if all 1’s are at least k places away from each other, otherwise return false.

Examples

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

Input: nums = [1,0,0,1,0,1], k = 2
Output: false
Explanation: The second 1 and third 1 are only one place apart.

Constraints

1 <= nums.length <= 10⁵
0 <= nums[i] <= 1
0 <= k <= 10⁵

• Linear Scan
• Pre-processing Indices
• Brute Force

Linear Scan

Intuition We can iterate through the array once, keeping track of the index of the last seen ‘1’. If we encounter another ‘1’, we simply check the distance between the current index and the previous index.

Steps

• Initialize a variable prev to -k - 1 (or a very small number) to handle the first ‘1’ correctly without special casing.
• Iterate through the array with index i.
• If nums[i] is 1:
  • Check if i - prev - 1 < k. If true, the distance is too short, return false.
  • Update prev to i.
• If the loop finishes, return true.

class Solution:
    def kLengthApart(self, nums: List[int], k: int) -> bool:
        prev = -k - 1
        for i, num in enumerate(nums):
            if num == 1:
                if i - prev - 1 < k:
                    return False
                prev = i
        return True

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Optimal solution with single pass and constant space.

Pre-processing Indices

Intuition First, collect all the indices where the value is 1 into a separate list. Then, iterate through this list to check the distance between consecutive indices.

Steps

• Create an empty list ones.
• Iterate through nums and append the index i to ones if nums[i] == 1.
• Iterate through ones from index 1 to the end.
• If ones[i] - ones[i-1] - 1 < k, return false.
• Return true.

class Solution:
    def kLengthApart(self, nums: List[int], k: int) -> bool:
        ones = [i for i, x in enumerate(nums) if x == 1]
        for i in range(1, len(ones)):
            if ones[i] - ones[i-1] - 1 < k:
                return False
        return True

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Uses extra space to store indices, but logic is very clear.

Brute Force

Intuition For every ‘1’ found in the array, look ahead at the next k elements to see if another ‘1’ exists within that range.

Steps

• Iterate through the array with index i.
• If nums[i] == 1:
  • Iterate through j from i + 1 to min(n - 1, i + k).
  • If nums[j] == 1, return false.
• Return true.

class Solution:
    def kLengthApart(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        for i in range(n):
            if nums[i] == 1:
                limit = min(n - 1, i + k)
                for j in range(i + 1, limit + 1):
                    if nums[j] == 1:
                        return False
        return True

Complexity

• Time: O(n * k)
• Space: O(1)
• Notes: Inefficient for large inputs where k is close to n.