You are given an array of integers nums of length n and a positive integer k.
The power of an array is defined as:
You need to find the power of all subarrays of nums of size k.
Return an integer array results of size n - k + 1, where results[i] is the power of nums[i..(i + k - 1)].
Example 1:
Input: nums = [1,2,3,4,3,2,5], k = 3
Output: [3,4,-1,-1,-1]
Explanation:
There are 5 subarrays of nums of size 3:
[1, 2, 3] with the maximum element 3.[2, 3, 4] with the maximum element 4.[3, 4, 3] whose elements are not consecutive.[4, 3, 2] whose elements are not sorted.[3, 2, 5] whose elements are not consecutive.Example 2:
Input: nums = [2,2,2,2,2], k = 4
Output: [-1,-1]
Example 3:
Input: nums = [3,2,3,2,3,2], k = 2
Output: [-1,3,-1,3,-1]
Constraints:
1 <= n == nums.length <= 1051 <= nums[i] <= 1061 <= k <= nProblem 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.
This approach uses a sliding window of size k. As we iterate through the array, we maintain a HashSet of the subarray elements. For each new element added, we ensure the subarray elements are consecutive by checking the difference between the maximum and minimum elements in the set.
The function iterates over all subarrays of size k, checking whether the subarray forms consecutive numbers. We check this by comparing the length of the unique set of elements with k and confirming if the range covered by elements is exactly k-1.
Python
The time complexity is O(n * k) due to iterating over each subarray of size k. The space complexity is O(k) for storing elements of each subarray.
This approach optimizes sorting by sorting within the sliding window. After sorting the subarray, we check the difference between consecutive elements. If all are exactly 1, we add the last element as the power. Otherwise, we return -1.
The function leverages sorting within each k-length subarray to easily check if numbers are consecutive. This reduces the complexity involved in each check.
Python
The time complexity is O(n * k log k) due to sorting each subarray. The space complexity remains O(k) for temporary storage.
In this approach, we utilize a sliding window technique to traverse through subarrays of size k. For each subarray, we perform the following steps:
The sliding window allows us to efficiently move through the array and avoid recomputation for the overlapping parts of the subarrays.
This implementation extracts a subarray of size k and checks if the elements are both sorted in ascending order and consecutive. If true, it extracts the maximum element of this subarray to store in the results; otherwise, -1 is stored.
In this approach, we optimize the sliding window by caching information at each step:
This reduces unnecessary calculations by leveraging computational history effectively.
This optimized version in C bypasses recalculations can occur during a sliding window approach by efficiently moving across the array and using previous computations where necessary.
We define an array f, where f[i] represents the length of the continuous increasing subsequence ending at the i-th element. Initially, f[i] = 1.
Next, we traverse the array nums to calculate the values of the array f. If nums[i] = nums[i - 1] + 1, then f[i] = f[i - 1] + 1; otherwise, f[i] = 1.
Then, we traverse the array f in the range [k - 1, n). If f[i] \ge k, we add nums[i] to the answer array; otherwise, we add -1.
After the traversal, we return the answer array.
The time complexity is O(n), and the space complexity is O(n). Here, n represents the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sliding Window with HashSet | The time complexity is O(n * k) due to iterating over each subarray of size k. The space complexity is O(k) for storing elements of each subarray. |
| Optimized with Sorting | The time complexity is O(n * k log k) due to sorting each subarray. The space complexity remains O(k) for temporary storage. |
| Sliding Window with Sorting Verification |
|
| Optimized Sliding Window with Cache |
|
| Recursion | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with HashSet | O(n * k) | O(k) | Simple correctness check for uniqueness and range |
| Sorting Each Window | O(n * k log k) | O(k) | When implementation simplicity is preferred |
| Sliding Window with Sorting Verification | O(n * k log k) | O(k) | Cross-language approach relying on built-in sorting |
| Optimized Sliding Window with Cache | O(n) | O(1) | Best choice for large arrays and interview settings |
Find the Power of K-Size Subarrays II || LeetCode Biweekly Contest 137 || Leetcode Solution • codi • 914 views views
Watch 9 more video solutions →Practice Find the Power of K-Size Subarrays II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor