Leetcode – Check If All 1’s Are at Least Length K Places Away Solution

Spread the love

The problem titled “Check If All 1’s Are at Least Length K Places Away” is an interesting challenge, mainly focusing on array traversal and distance calculation. This problem can be categorized under array manipulation and searching algorithms.

In this comprehensive article, we will cover:

  1. The Problem Statement
  2. A Naive Approach to the Problem
  3. An Optimized Solution
  4. Python Code Implementations
  5. Test Cases and Performance Analysis
  6. Time and Space Complexity Analysis
  7. Conclusion

1. Problem Statement

Problem Statement

You are given an array nums of 1’s and 0’s, 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: False
Explanation: The second and third 1’s are only 2 places apart from each other.

Example 2:

Input: nums = [1,0,0,1,0,1], k = 2
Output: False
Explanation: The first and second 1’s are 2 places apart, which is less than or equal to k.

2. A Naive Approach to the Problem

A straightforward way to solve this problem is to:

  1. Traverse the array and store the indices of all 1’s in a list.
  2. Iterate through this list to check if the distance between adjacent 1’s is at least k.

3. An Optimized Solution

Instead of storing all indices first and then checking distances, you can combine both steps:

  1. Keep track of the last position where a ‘1’ was found.
  2. As you traverse the array, if you find another ‘1’, check its distance to the last one immediately.

This will reduce the space complexity of the solution.

4. Python Code Implementations

Naive Implementation

def kLengthApart(nums, k):
    ones_indices = [i for i, num in enumerate(nums) if num == 1]
    
    for i in range(1, len(ones_indices)):
        if ones_indices[i] - ones_indices[i-1] <= k:
            return False
            
    return True

Optimized Implementation

def kLengthApart(nums, k):
    last_one_index = -1
    
    for i, num in enumerate(nums):
        if num == 1:
            if last_one_index != -1 and i - last_one_index <= k:
                return False
            last_one_index = i
            
    return True

5. Test Cases and Performance Analysis

Let’s validate the solutions with some test cases:

# Test 1
assert kLengthApart([1,0,0,0,1,0,0,1], 2) == False
# Test 2
assert kLengthApart([1,0,0,1,0,1], 2) == False
# Test 3 (Edge case)
assert kLengthApart([1,0,0,0,0,0,1], 5) == True

Both solutions pass these tests, but the optimized solution does it more efficiently.

6. Time and Space Complexity Analysis

Time Complexity

Both the naive and the optimized solutions have a time complexity of O(n), where n is the length of the array. This is because we are traversing the list once.

Space Complexity

The space complexity for the naive solution is O(n) because we store all 1’s indices in a separate list. The space complexity for the optimized solution is O(1), as we only keep track of the last 1’s index.

7. Conclusion

The “Check If All 1’s Are at Least Length K Places Away” problem is an excellent problem for practicing array manipulation and distance calculation in Python. It tests your skills in efficiently traversing arrays and making comparisons.

In this article, we explored both a naive approach and an optimized approach to solving the problem, including Python implementations for both. We covered test cases to validate the solution and performed time and space complexity analysis.

Leave a Reply