We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

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

Difficulty: Easy

Problem Description

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

Key Insights

  • The problem requires checking the distances between each pair of 1s in the array.
  • A simple linear pass through the array can help keep track of the last position of 1 encountered.
  • If the distance between two 1s is less than k, the function should return false.
  • If the loop completes without finding any violations, return true.

Space and Time Complexity

Time Complexity: O(n) - We traverse the array once. Space Complexity: O(1) - We use a constant amount of space.

Solution

To solve this problem, we can use a straightforward linear traversal of the binary array nums. We will maintain a variable to keep track of the last index where we found a 1. As we iterate through the array, each time we encounter a 1, we will check its index against the last recorded index. If the difference between these indices is less than k, we return false. If we finish the iteration without returning false, we return true.

Code Solutions

def k_length_apart(nums, k):
    last_position = -1  # Initialize last position of '1' as -1
    for i in range(len(nums)):
        if nums[i] == 1:  # Check if the current element is '1'
            if last_position != -1 and i - last_position < k:  # Check distance from last '1'
                return False  # If the distance is less than k, return False
            last_position = i  # Update the last position of '1' to current index
    return True  # If all '1's are at least k apart, return True
← Back to All Questions