What is the approach for solving 'Check If All 1's Are at Least Length K Places Away'?

The best approach is to iterate through the array and check the distance between each pair of consecutive 1's. If any pair is too close, return false.

What is the time complexity for this problem?

The time complexity of the optimal solution is O(n), where n is the length of the array, since we only need to iterate through the array once.

Can the problem be solved in constant space?

Yes, the problem can be solved with O(1) space by simply keeping track of the index of the last 1 encountered during the iteration.

How do I handle edge cases in this problem?

Handle cases where there are fewer than two 1's by returning true immediately, as they are trivially at least k places apart.

What is a variant of the 'Check If All 1's Are at Least Length K Places Away' problem?

One variant could involve making the array circular, where the first and last 1's need to also be at least k places apart.

#1437

Easy

auto_awesome数组·driven

LeetCode 题解工作台

是否所有 1 都至少相隔 k 个元素

给你一个由若干 0 和 1 组成的数组 nums 以及整数 k 。如果所有 1 都至少相隔 k 个元素，则返回 true ；否则，返回 false 。示例 1：输入： nums = [1,0,0,0,1,0,0,1], k = 2 输出： true 解释：每个 1 都至少相隔 2 个元素。示…

数组

题目描述

给你一个由若干 0 和 1 组成的数组 nums 以及整数 k。如果所有 1 都至少相隔 k 个元素，则返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,0,0,0,1,0,0,1], k = 2
输出：true
解释：每个 1 都至少相隔 2 个元素。

示例 2：

输入：nums = [1,0,0,1,0,1], k = 2
输出：false
解释：第二个 1 和第三个 1 之间只隔了 1 个元素。

提示：

1 <= nums.length <= 10⁵
0 <= k <= nums.length
nums[i] 的值为 0 或 1

lightbulb

解题思路

方法一：模拟

我们可以遍历数组 $\textit{nums}$ ，用变量 $j$ 记录上一个 $1$ 的下标，那么当前位置 $i$ 的元素为 $1$ 时，只需要判断 $i - j - 1$ 是否小于 $k$ 即可。如果小于 $k$ ，则说明存在两个 $1$ 之间的 $0$ 的个数小于 $k$ ，返回 $\text{false}$ ；否则，将 $j$ 更新为 $i$ ，继续遍历数组。

遍历结束后，返回 $\text{true}$ 。

时间复杂度 $O(n)$ ，其中 $n$ 为数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def kLengthApart(self, nums: List[int], k: int) -> bool:
        j = -inf
        for i, x in enumerate(nums):
            if x:
                if i - j - 1 < k:
                    return False
                j = i
        return True

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate correctly identifies an array-driven approach.
question_mark
The candidate is able to identify and handle early termination to optimize performance.
question_mark
The candidate does not attempt overly complex solutions when a simpler approach works well.

warning

常见陷阱

外企场景

error
Not handling the case where there are fewer than two 1's in the array, which should immediately return true.
error
Assuming the array always has two 1's or more without checking edge cases.
error
Failing to exit early when the distance condition is violated, leading to unnecessary checks.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the problem to check for a different minimum distance between 1's.
arrow_right_alt
Allow the array to be a circular buffer where the first and last 1 can be considered neighbors.
arrow_right_alt
Add multiple values for k and return an array of boolean results for each value.

help

常见问题

外企场景

继续练习

#1436 旅行终点站 #1438 绝对差不超过限制的最长连续子数组 #1439 有序矩阵中的第 k 个最小数组和