⚡Flashcard Drill➔
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

  1. A set of k integers can be rearranged into consecutive increasing values exactly when the values are {x, x+1, ..., x+k-1} for some x.
  2. In the original subarray order, this means nums[j+1] == nums[j] + 1 for every adjacent pair.
  3. So a window is powerful exactly when every adjacent pair inside it increases by exactly 1.
  4. 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 == 1 case: every single element is trivially consecutive, so the answer is the array itself. The general code would use cur == 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 is ok[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.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems