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

Problem Statement

In this problem, we are given a binary array nums comprising only the elements 0 and 1. We are also provided with an integer k. The task is to determine whether all the '1s' in the array nums are at least k places apart from each other. If they are, the function should return true, otherwise it should return false. The challenge lies in efficiently verifying the spacing between each occurrence of '1' given that the length of the array can be very large.

Examples

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 1 and third 1 are only one apart from each other.

Constraints

• 1 <= nums.length <= 105
• 0 <= k <= nums.length
• nums[i] is 0 or 1

Approach and Intuition

To solve this problem, we can use a simple iterative approach to check the spacing between consecutive '1s' in the array:

1. Initialize a variable, say last_position, to -1. This will store the index of the most recent '1' found in the array.
2. Iterate over the array from the first to the last element:
   • If the current element is 1:
     • Calculate the distance from last_position if last_position is not -1.
     • If this distance is less than k, immediately return false as the condition is violated.
     • Update last_position to the current index.
3. If the loop completes without finding any pairs of consecutive '1s' that violate the distance condition, return true.

Example illustration from provided instances:

• For the input nums = [1,0,0,0,1,0,0,1], k = 2, the sequence checks as follows:

  • First '1' at index 0, set last_position to 0.
  • Next '1' at index 4, the difference is 4 - 0 - 1 = 3, which is greater than 2.
  • Last '1' at index 7, the difference is 7 - 4 - 1 = 2, which is equal to the condition, hence it satisfies.
  • Result is true for this setup.

• For nums = [1,0,0,1,0,1], k = 2, it checks as follows:

  • First '1' at index 0, set last_position to 0.
  • Second '1' at index 3, the difference is 3 - 0 - 1 = 2, which is equal to k.
  • Third '1' at index 5, the difference is 5 - 3 - 1 = 1, which does not satisfy the condition (less than 2).
  • A false condition is detected, and false is the output.

By utilizing this method, we can efficiently determine if all '1s' in the array are at least k places apart, adhering strictly to the conditions laid out in the problem constraints.

Solutions

class Solution {
    public boolean checkDistance(int[] array, int distance) {
        int concatenated = 0;
        for (int element : array) {
            concatenated = (concatenated << 1) | element;
        }
            
        if (concatenated == 0 || distance == 0) {
            return true;
        }
            
        while ((concatenated & 1) == 0) {
            concatenated >>= 1;    
        }
            
        while (concatenated != 1) {
            concatenated >>= 1;
                
            int zeroCount = 0;
            while ((concatenated & 1) == 0) {
                concatenated >>= 1;
                zeroCount++;
            }
                
            if (zeroCount < distance) {
                return false;
            }
        }
        return true;
    }
}