algoadvance

Leetcode 1437. Check If All 1’s Are at Least Length K Places Away

Problem Statement

You are given an array of integers nums and an integer k. The array only contains the integers 0 and 1. Return true if all 1s 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 and third 1s are only one position apart from each other.

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= k <= nums.length - 1
• nums[i] is 0 or 1

Clarifying Questions

1. Are there any edge cases to consider?
   • An edge case might be where the array contains all 0s or only one 1.
2. How should we handle cases where k is greater than the length of the array?
   • It is given that 0 <= k <= nums.length - 1, so we don’t need to handle those cases.
3. Is it guaranteed that the input will always be valid?
   • Yes, according to the constraints.

Strategy

1. Initialize a variable last_index to store the index of the previous 1 encountered and set it to -1 initially.
2. Iterate through the array:
   • When you encounter a 1, check if last_index is not -1 (indicating it’s not the first 1 you are encountering).
   • If it is not, calculate the distance from the last encountered 1 and see if it is less than k.
   • If the distance is less than k, return false.
   • Update last_index to the current index.
3. If the loop completes without returning false, return true.

Code

#include <vector>
using namespace std;

bool kLengthApart(vector<int>& nums, int k) {
    int last_index = -1;  // To store the index of the last encountered `1`

    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] == 1) {
            if (last_index != -1) {  // Check the distance from the last `1`
                if (i - last_index - 1 < k) {
                    return false;  // Distance is less than `k`
                }
            }
            last_index = i;  // Update the last index to the current index
        }
    }

    return true;
}

Time Complexity

• The time complexity is O(n), where n is the length of the nums array. This is because we only perform a single pass through the array.
• The space complexity is O(1), as we are using a fixed amount of extra space regardless of the input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?