NeetCode #247LC-3254MediumSliding Window
← Back to All Problems#247 · #3254 · Find the Power of K-Size Subarrays I(长度为 K 的子数组的能量值 I)
📌 Problem Statement & Constraints
You are given an array
nums of n integers and an integer k. For each subarray of size k, it is powerful if its elements can be rearranged into k consecutive increasing integers. Return an array where the i-th element is the last element of the i-th subarray if it is powerful, otherwise -1. Constraints: 1 <= n == nums.length <= 500, 1 <= nums[i] <= 10^5, 1 <= k <= n.💡 Core Algorithmic Approaches
- A set of
kintegers can be rearranged into consecutive increasing values exactly when the values are{x, x+1, ..., x+k-1}for somex. - In the original subarray order, this means
nums[j+1] == nums[j] + 1for every adjacent pair. - So a window is powerful exactly when every adjacent pair inside it increases by exactly 1.
- Precompute a boolean array for adjacent pairs and use a running count of violations to make each window check O(1).
💻 Benchmark Python3 Implementation
class Solution:
def resultsArray(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
if k == 1:
return nums[:] # a single element is trivially consecutive
# ok[i] = 1 if nums[i] + 1 == nums[i+1]
ok = [1 if nums[i] + 1 == nums[i + 1] else 0 for i in range(n - 1)]
res = []
cur = sum(ok[:k - 1]) # number of matching edges in the first window
for i in range(n - k + 1):
if i > 0:
cur -= ok[i - 1] # the edge leaving the window
cur += ok[i + k - 2] # the edge entering
res.append(nums[i + k - 1] if cur == k - 1 else -1)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass with O(1) work per window.
💾 Space Complexity
O(n) for the adjacency array (O(1) if computed on the fly).
⚠️ Interview Pitfalls & Follow-ups
- Sorting each window and checking consecutiveness: O(n * k log k) instead of O(n).
- Counting violations rather than matches: either works, but the comparison must be consistent with the threshold
k - 1. - Forgetting the
k == 1case: every single element is trivially consecutive, so the answer is the array itself. The general code would usecur == 0, which also works, but the explicit branch is clearer. - Off-by-one on the entering edge: for window starting at
i, the new edge isok[i + k - 2].
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner