Find the Power of K-Size Subarrays II - Video Solutions

Problem Overview: You are given an integer array and a window size k. For every contiguous subarray of length k, determine whether its elements form k consecutive integers. If they do, the subarray's power is the maximum element in that window; otherwise return -1. The result is an array of length n - k + 1.

Approach 1: Sliding Window with HashSet (O(n * k) time, O(k) space)

Iterate through every window of size k using a sliding window. Insert elements into a HashSet while also tracking the minimum and maximum values. If the set size equals k and max - min == k - 1, the numbers form consecutive integers, so the power equals max. Otherwise return -1 for that window. This approach is easy to reason about and directly verifies uniqueness and range, but rebuilding the set for each window makes it slower for large inputs.

Approach 2: Optimized with Sorting (O(n * k log k) time, O(k) space)

For each window, copy the k elements and sort them using standard sorting. After sorting, check whether every adjacent pair satisfies arr[i] + 1 == arr[i + 1]. If the condition holds for all elements, the window forms a consecutive sequence and the power is the last element of the sorted list. Sorting simplifies the verification logic but increases the per-window cost, which becomes expensive when k is large.

Approach 3: Sliding Window with Sorting Verification (O(n * k log k) time, O(k) space)

This approach still uses a window over the array but focuses on verifying the consecutive property through sorted order checks. Each window is validated by sorting and scanning for consecutive differences. Although the algorithm is straightforward and works well in languages with fast built‑in sorting, it does not fully exploit overlap between neighboring windows.

Approach 4: Optimized Sliding Window with Cache (O(n) time, O(1) space)

The key observation: if a window of size k contains consecutive integers in increasing order, then every adjacent pair must satisfy nums[i] + 1 == nums[i + 1]. Instead of rechecking the whole window, maintain a cached count of consecutive relationships while sliding the window. When a pair breaks the rule, reset the streak. If the current streak length reaches at least k, the window ending at that index forms a valid sequence and its power equals nums[i]. This eliminates repeated verification and achieves linear time.

Recommended for interviews: Start by describing the brute-force window validation (HashSet or sorting). It clearly shows how to verify uniqueness and consecutive range. Then move to the optimized sliding window insight that reuses information between windows. Interviewers typically expect the O(n) sliding window solution because it demonstrates strong understanding of window invariants and incremental updates.