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 <= 5001 <= nums[i] <= 1051 <= k <= nProblem Overview: You are given an integer array and a window size k. For every contiguous subarray of length k, determine whether the elements form a strictly increasing consecutive sequence where nums[i] + 1 = nums[i+1]. If the condition holds, the subarray's power is the maximum element (the last element of that window). Otherwise, the power is -1. The result is an array containing the power of each k-length window.
Approach 1: Brute Force Checking of Subarrays (Time: O(n*k), Space: O(1))
The straightforward solution checks every subarray of size k. For each starting index, iterate through the next k-1 elements and verify the consecutive condition nums[j] + 1 == nums[j+1]. If any pair breaks the rule, the current window is invalid and its power becomes -1. If all comparisons succeed, return the last element of that window as the power. This method directly follows the problem definition and is useful for validating logic during implementation. However, because each window requires up to k comparisons, the total runtime grows to O(n*k) for an array of size n. The approach uses constant extra space since it only tracks indices and comparisons.
Approach 2: Optimized Sliding Window Technique (Time: O(n), Space: O(1))
The optimized solution observes that consecutive windows overlap heavily. Instead of rechecking all k elements each time, track the length of the current streak where adjacent numbers increase by exactly one. Iterate through the array once and update a counter whenever nums[i] == nums[i-1] + 1. If the condition breaks, reset the streak length. For a window ending at index i, the subarray of size k is valid if the streak length is at least k. When valid, record nums[i] as the power; otherwise record -1. This effectively converts repeated window validation into a single pass over the array. The algorithm runs in linear time O(n) with constant space.
This pattern is common in problems involving contiguous segments and overlapping windows. Understanding how to reuse information from the previous window is the key optimization in sliding window techniques. Since the data is processed sequentially, the solution relies only on simple comparisons and counters over the array.
Recommended for interviews: Start by describing the brute force approach to show you understand the requirement for validating each window. Then transition to the sliding window optimization that tracks consecutive increments in a single pass. Interviewers typically expect the O(n) sliding window solution because it demonstrates pattern recognition and efficient handling of overlapping subarrays.
We can solve this problem by checking all possible subarrays of size k explicitly. For each subarray, we check if it is sorted and if the elements are consecutive. If both conditions are met, we calculate the power as the maximum element of the subarray. Otherwise, the power is -1.
This C implementation uses a function to check whether each subarray of size k is sorted and the elements are consecutive. If both conditions are satisfied, the function calculates the power as the maximum element of the subarray.
Time Complexity: O(n * k) because we process each element of each subarray of size k.
Space Complexity: O(n-k+1) for storing the results array.
This approach employs a sliding window technique to process each subarray of size k efficiently. We slide over the array and check whether each segment meets the criteria of being both sorted and consecutive. This reduces unnecessary re-checks by leveraging overlapping subarray properties.
This C implementation uses a function to verify both order and consecutiveness of elements in a k-length sliding window. The maximum element is calculated if the conditions are met.
Time Complexity: O(n * k), reduced by potentially not rechecking unchanged segments.
Space Complexity: O(n-k+1) for the results array.
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
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Brute Force Checking of Subarrays | Time Complexity: |
| Optimized Sliding Window Technique | Time Complexity: |
| Recursion | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Checking of Subarrays | O(n*k) | O(1) | Good for understanding the problem or when k is very small |
| Sliding Window with Consecutive Streak Tracking | O(n) | O(1) | Preferred for large arrays and interview settings where optimal performance is required |
Find the Power of K-Size Subarrays I - Leetcode 3254 - Python • NeetCodeIO • 9,128 views views
Watch 9 more video solutions →Practice Find the Power of K-Size Subarrays I with our built-in code editor and test cases.
Practice on FleetCode