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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

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

Number: 1548

Difficulty: Easy

Paid? No

Companies: United Health Group

Problem Description

Given a binary array nums and an integer k, determine whether all 1's in the array are at least k places apart from each other. If they are, return true; otherwise, return false.

Key Insights

  • Iterate through the array while keeping track of the index of the last encountered 1.
  • For every new 1, check if the distance from the previous 1 is at least k + 1.
  • If the gap is too small, immediately return false.
  • A single sweep of the array is sufficient (O(n) time complexity).

Space and Time Complexity

Time Complexity: O(n) Space Complexity: O(1)

Solution

We solve this problem by traversing the array once and using a variable to store the index of the last seen 1. When a 1 is found, if there was a previous 1, we check if the current index minus the previous index is less than k + 1. If so, we return false immediately. If no violations are found after processing the entire array, we return true. This approach uses a simple iteration with an integer variable for tracking, leading to O(n) time and O(1) space complexity.

Code Solutions

# Python solution with line-by-line comments

def k_length_apart(nums, k):
    last_one_index = -k - 1  # Initialize to a value ensuring first 1 check passes
    for i, num in enumerate(nums):
        if num == 1:
            # Check if the gap between current and last 1 is less than k+1
            if i - last_one_index < k + 1:
                return False
            last_one_index = i   # Update the last seen 1's index
    return True

# Example usage:
# print(k_length_apart([1,0,0,0,1,0,0,1], 2)) returns True
# print(k_length_apart([1,0,0,1,0,1], 2)) returns False
← Back to All Questions