algoadvance

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

Problem Statement

You are 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.

Example

  1. Input: nums = [1,0,0,0,1,0,0,1], k = 2 Output: true
  2. Input: nums = [1,0,0,1,0,1], k = 2 Output: false

Clarifying Questions

  1. Range of inputs: What are the length constraints on nums and k?
    • Length of nums can range from 2 to 10^5.
    • k is a non-negative integer and will be less than or equal to the length of nums.
  2. Edge cases:
    • Arrays with no 1’s or only one 1.
    • Large values of k that are greater than the length of nums.

Strategy

  1. Initialize a variable previousIndex to keep track of the index of the last 1 encountered.
  2. Iterate through the nums array:
    • For each 1 encountered, check the distance from the previousIndex.
    • If the distance is less than k, return false.
    • Update previousIndex to the current index.
  3. If the loop completes without any issue, return true.

Code

public class Solution {
    public boolean kLengthApart(int[] nums, int k) {
        int previousIndex = -1; // Initially no 1 encountered
        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                if (previousIndex != -1 && i - previousIndex - 1 < k) {
                    return false; // Distance between the current 1 and the previous 1 is less than k
                }
                previousIndex = i; // Update previousIndex to the current index
            }
        }
        
        return true;
    }
}

Time Complexity

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