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

Easy
495.

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

Check If All 1's Are at Least Length K Places Away is an easy coding problem on arrays, asked in Amazon and Meta interviews.

Given a binary array nums and an integer k, return true if every pair of adjacent 1's is separated by at least k zeros.

Example 1

Input
nums = [1,0,0,0,1,0,0,1], k = 2
Output
true
Explanation
The gaps hold 3 zeros and 2 zeros, both at least 2.

Example 2

Input
nums = [1,0,0,1,0,1], k = 2
Output
false
Explanation
The last two 1's have only one zero between them.

Example 3

Input
nums = [1,1,1,1,1], k = 0
Output
true

Constraints

  • 1 <= nums.length <= 100000
  • 0 <= k <= nums.length
  • nums[i] is 0 or 1.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var kLengthApart = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Check If All 1's Are at Least Length K Places Away solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Check If All 1's Are at Least Length K Places Away is an easy coding problem on arrays, asked in Amazon and Meta interviews.

  • Difficulty: Easy
  • Topics: Arrays
  • Asked at: Amazon, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given a binary array nums and an integer k, return true if every pair of adjacent 1's is separated by at least k zeros.

Example 1

Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: true
Explanation: The gaps hold 3 zeros and 2 zeros, both at least 2.

Example 2

Input: nums = [1,0,0,1,0,1], k = 2
Output: false
Explanation: The last two 1's have only one zero between them.

Example 3

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

Constraints

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

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

  1. Hint 1

    Only consecutive 1's matter — you never need to compare non-adjacent ones.

  2. Hint 2

    Remember the index of the previous 1 as you scan.

  3. Hint 3

    The number of zeros between index prev and index i is i - prev - 1.

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

Track the position of the most recent 1. When the next 1 arrives, the zeros between them are fully determined by the two indices.

Approach

  1. Initialise prev = -1 meaning "no 1 seen yet".
  2. For each index i where nums[i] == 1: if prev != -1 and i - prev - 1 < k, return false.
  3. Otherwise set prev = i and continue.
  4. Return true if the scan completes.

Why it works

If every adjacent pair is far enough apart then every pair is, since gaps only grow when you skip intervening 1's. So checking adjacent pairs is both necessary and sufficient.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Using i - prev instead of i - prev - 1 counts one of the endpoints as a zero and lets a too-tight pair through.
  • The first 1 has no predecessor — comparing against prev = -1 without the guard produces a false negative.
  • k = 0 must accept adjacent 1's.

Reference solution

Python

from typing import List

def kLengthApart(nums: List[int], k: int) -> bool:
    prev = -1
    for i, x in enumerate(nums):
        if x == 1:
            if prev != -1 and i - prev - 1 < k:
                return False
            prev = i
    return True

Java

public static boolean kLengthApart(int[] nums, int k) {
    int prev = -1;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 1) {
            if (prev != -1 && i - prev - 1 < k) return false;
            prev = i;
        }
    }
    return true;
}

C++

bool kLengthApart(vector<int>& nums, int k) {
    int prev = -1;
    for (int i = 0; i < (int) nums.size(); i++) {
        if (nums[i] == 1) {
            if (prev != -1 && i - prev - 1 < k) return false;
            prev = i;
        }
    }
    return true;
}

JavaScript

var kLengthApart = function(nums, k) {
    let prev = -1;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === 1) {
            if (prev !== -1 && i - prev - 1 < k) return false;
            prev = i;
        }
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays