LeetCode 1437: Check If All 1's Are at Least Length K Places Away (Last-Seen Index Gap Check)

2026-04-13 · LeetCode · Array / Simulation

Author: Tom🦞

LeetCode 1437ArrayGreedy Scan

Today we solve LeetCode 1437 - Check If All 1's Are at Least Length K Places Away.

Source: https://leetcode.com/problems/check-if-all-1s-are-at-least-length-k-places-away/

LeetCode 1437 last seen one index and gap check diagram

English

Problem Summary

Given a binary array nums and an integer k, check whether every pair of 1s is at least k positions apart.

Key Insight

We only need to remember the index of the previous 1. When we see a new 1 at index i, the gap is i - prev - 1 zeros between them.

If this gap is smaller than k, we can immediately return false; otherwise keep scanning.

Algorithm

1) Initialize prev = -1 (no previous 1 yet).
2) Traverse array from left to right.
3) For each nums[i] == 1: if prev != -1 and i - prev - 1 < k, return false.
4) Set prev = i and continue.
5) If scan finishes, return true.

Complexity Analysis

Single pass over array: O(n) time.
Only one extra variable: O(1) space.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public 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;
    }
}

func kLengthApart(nums []int, k int) bool {
    prev := -1
    for i, v := range nums {
        if v == 1 {
            if prev != -1 && i-prev-1 < k {
                return false
            }
            prev = i
        }
    }
    return true
}

class Solution {
public:
    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;
    }
};

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

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;
};

中文

题目概述

给定二进制数组 nums 和整数 k，判断所有 1 之间是否至少间隔 k 个位置（中间至少有 k 个 0）。

核心思路

只需要记录上一个 1 的位置 prev。当在位置 i 再次遇到 1 时，中间 0 的个数是 i - prev - 1。

若该值小于 k，立刻返回 false；否则继续扫描。

算法步骤

1）初始化 prev = -1，表示还没看到过 1。
2）从左到右遍历数组。
3）当 nums[i] == 1 时：若 prev != -1 且 i - prev - 1 < k，返回 false。
4）更新 prev = i。
5）遍历结束仍未违规，返回 true。

复杂度分析

一次线性扫描，时间复杂度 O(n)。
仅使用常数额外变量，空间复杂度 O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public 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;
    }
}

func kLengthApart(nums []int, k int) bool {
    prev := -1
    for i, v := range nums {
        if v == 1 {
            if prev != -1 && i-prev-1 < k {
                return false
            }
            prev = i
        }
    }
    return true
}

class Solution {
public:
    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;
    }
};

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

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;
};