Find the Power of K-Size Subarrays II
MedPrompt
You are given an array of integers nums of length n and a positive integer k.
The power of an array is defined as:
- Its maximum element if all of its elements are consecutive and sorted in ascending order.
- -1 otherwise.
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 <= n
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the problem statement into code. It iterates through each possible subarray of size k, and for each one, it performs a linear scan to check if it meets the specified conditions: being sorted in ascending order and having consecutive elements. This is the most straightforward but also the least efficient method.
Algorithm
- Initialize an empty
resultsarray of sizen - k + 1. - Loop with an index
ifrom0ton - k. Thisirepresents the starting index of a subarray. - For each
i, assume the subarray is valid by setting a boolean flag, e.g.,isValid = true. - Start a nested loop with index
jfromi + 1toi + k - 1. - Inside the nested loop, check if
nums[j]is equal tonums[j-1] + 1. - If the condition is ever false, the subarray is invalid. Set
isValid = falseand break the inner loop. - After the inner loop, if
isValidis still true, the subarray's power is its last element,nums[i + k - 1]. Otherwise, its power is-1. - Store the calculated power in
results[i]. - After the outer loop finishes, return the
resultsarray.
Walkthrough
The brute-force method examines every single subarray of length k independently. For each subarray starting at index i, it iterates from the second element to the end of the subarray, verifying the condition nums[j] == nums[j-1] + 1. If this condition holds for all elements in the subarray, the power is the maximum element (which is the last element, nums[i+k-1]). If the condition fails at any point, the power is -1, and we can immediately move to the next subarray.
class Solution { public long[] getPowerOfKSizeSubarrays(int[] nums, int k) { int n = nums.length; if (k == 0) { return new long[0]; } long[] results = new long[n - k + 1]; for (int i = 0; i <= n - k; i++) { boolean isConsecutiveAndSorted = true; // Check the subarray nums[i...i+k-1] for (int j = i + 1; j < i + k; j++) { if (nums[j] != nums[j - 1] + 1) { isConsecutiveAndSorted = false; break; } } if (isConsecutiveAndSorted) { results[i] = nums[i + k - 1]; } else { results[i] = -1; } } return results; }}Complexity
Time
O(n * k). The outer loop runs `n - k + 1` times, and for each iteration, the inner loop runs `k - 1` times. This leads to a quadratic time complexity in the worst case where `k` is proportional to `n`.
Space
O(1) auxiliary space. The space required for the output array `results` is O(n-k+1), but auxiliary space is constant as we only use a few variables for loops and flags.
Trade-offs
Pros
Simple to understand and implement.
Correctly solves the problem without complex logic.
Cons
Highly inefficient for large
nandk.Very likely to result in a Time Limit Exceeded (TLE) error on competitive programming platforms for the given constraints.
This method improves upon the brute-force approach by pre-calculating information to avoid redundant checks. It uses a dynamic programming technique to compute the length of consecutive runs of numbers in a single pass. A subarray nums[i...i+k-1] is valid if and only if the run of consecutive numbers ending at index i+k-1 is at least k long. This pre-computation allows us to determine the power of each subarray in constant time.
Algorithm
- Create an integer array,
runLength, of the same size asnums.runLength[j]will store the length of the consecutive, sorted sequence ending at indexj. - Initialize
runLength[0] = 1. - Iterate from
j = 1ton - 1. Ifnums[j] == nums[j-1] + 1, setrunLength[j] = runLength[j-1] + 1. Otherwise, a new run starts, so setrunLength[j] = 1. - Initialize the
resultsarray of sizen - k + 1. - Iterate from
i = 0ton - k. Thisiis the start of the window. - The window ends at index
endIdx = i + k - 1. - Check if
runLength[endIdx] >= k. If it is, the entire window is part of a valid run. The power isnums[endIdx]. - If
runLength[endIdx] < k, the window is not a valid run. The power is-1. - Store the result in
results[i]. - Return the
resultsarray.
Walkthrough
The core idea is to transform the problem. A subarray nums[i...i+k-1] is consecutive and sorted if and only if nums[j] == nums[j-1] + 1 for all j from i+1 to i+k-1. We can create an auxiliary array, runLength, where runLength[j] stores the length of the valid consecutive sequence ending at that index j. This array can be built in O(n) time. Once we have this runLength array, we can find the power for each k-size subarray in O(1) time. For a subarray ending at index endIdx, we just need to check if runLength[endIdx] is at least k.
class Solution { public long[] getPowerOfKSizeSubarrays(int[] nums, int k) { int n = nums.length; if (k == 0) { return new long[0]; } if (k == 1) { long[] results = new long[n]; for (int i = 0; i < n; i++) { results[i] = nums[i]; } return results; } // runLength[i] stores the length of the consecutive run ending at index i int[] runLength = new int[n]; runLength[0] = 1; for (int i = 1; i < n; i++) { if (nums[i] == nums[i - 1] + 1) { runLength[i] = runLength[i - 1] + 1; } else { runLength[i] = 1; } } long[] results = new long[n - k + 1]; for (int i = 0; i <= n - k; i++) { int windowEndIndex = i + k - 1; // Check if the run of consecutive numbers ending at windowEndIndex // is long enough to cover the entire window. if (runLength[windowEndIndex] >= k) { results[i] = nums[windowEndIndex]; } else { results[i] = -1; } } return results; }}Complexity
Time
O(n). We perform two separate linear passes over the data: one to compute `runLength` and another to compute `results`. Both take `O(n)` time.
Space
O(n). We need an auxiliary array `runLength` of size `n` to store the pre-computed run lengths.
Trade-offs
Pros
Much faster than the brute-force approach with a linear time complexity.
The logic is still relatively straightforward to follow.
Cons
Requires extra space proportional to the input size, which might be a concern for very large inputs under strict memory constraints.
This is the most efficient approach in terms of both time and space. It uses a sliding window of size k and maintains a count of adjacent pairs that satisfy the consecutive condition (nums[j] == nums[j-1] + 1). A subarray is valid if and only if it contains k-1 such pairs. As the window slides, this count is updated in constant time by subtracting the contribution of the element that leaves the window and adding the contribution of the element that enters. This avoids redundant calculations entirely.
Algorithm
- Initialize a
resultsarray of sizen - k + 1. - Initialize a counter,
consecutivePairs, to 0. - First Window: Iterate from
j = 1tok - 1to populate the counter for the initial windownums[0...k-1]. Ifnums[j] == nums[j-1] + 1, incrementconsecutivePairs. - After the initial setup, check if
consecutivePairs == k - 1. If so, the first subarray is valid, andresults[0]isnums[k-1]. Otherwise,results[0]is-1. - Slide the Window: Loop from
i = 1ton - k. In each iteration, the window slides one position to the right. - Update for leaving element: The pair
(nums[i-1], nums[i])is leaving the window's scope. If this pair was consecutive (nums[i] == nums[i-1] + 1), decrementconsecutivePairs. - Update for entering element: The pair
(nums[i+k-2], nums[i+k-1])is entering the window's scope. If this new pair is consecutive, incrementconsecutivePairs. - After updating the counter, check if
consecutivePairs == k - 1. If it is, the current windownums[i...i+k-1]is valid. Setresults[i] = nums[i+k-1]. Otherwise, setresults[i] = -1. - Return the
resultsarray.
Walkthrough
We start by analyzing the first window of size k and counting how many adjacent pairs are consecutive. A window is valid if this count is exactly k-1. Then, as we slide the window one position to the right, we don't need to re-scan the whole window. We only need to consider two pairs: the one leaving the window from the left and the one entering from the right. We adjust our count based on these two pairs. This O(1) update per slide allows us to process the entire array in linear time with constant extra space.
class Solution { public long[] getPowerOfKSizeSubarrays(int[] nums, int k) { int n = nums.length; if (k == 0) { return new long[0]; } long[] results = new long[n - k + 1]; if (k == 1) { for (int i = 0; i < n; i++) { results[i] = nums[i]; } return results; } // Initialize for the first window int consecutivePairs = 0; for (int i = 1; i < k; i++) { if (nums[i] == nums[i - 1] + 1) { consecutivePairs++; } } if (consecutivePairs == k - 1) { results[0] = nums[k - 1]; } else { results[0] = -1; } // Slide the window for (int i = 1; i <= n - k; i++) { // Element leaving the window is nums[i-1]. // The pair (nums[i-1], nums[i]) is no longer part of the window's checks. if (nums[i] == nums[i - 1] + 1) { consecutivePairs--; } // Element entering the window is nums[i+k-1]. // The new pair to check is (nums[i+k-2], nums[i+k-1]). if (nums[i + k - 1] == nums[i + k - 2] + 1) { consecutivePairs++; } if (consecutivePairs == k - 1) { results[i] = nums[i + k - 1]; } else { results[i] = -1; } } return results; }}Complexity
Time
O(n). The initial window setup takes `O(k)`. The subsequent `n-k` slides each take `O(1)` time for updates. The total time is `O(k + (n-k)) = O(n)`.
Space
O(1) auxiliary space. We only use a few variables to keep track of the count and loop indices, regardless of the input size.
Trade-offs
Pros
Optimal time complexity of O(n).
Optimal auxiliary space complexity of O(1).
Highly efficient for large inputs.
Cons
The logic for updating the counter at the window boundaries can be slightly more complex to implement correctly compared to other approaches.
Solutions
Solution
class Solution {public int[] resultsArray(int[] nums, int k) { int n = nums.length; int[] f = new int[n]; Arrays.fill(f, 1); for (int i = 1; i < n; ++i) { if (nums[i] == nums[i - 1] + 1) { f[i] = f[i - 1] + 1; } } int[] ans = new int[n - k + 1]; for (int i = k - 1; i < n; ++i) { ans[i - k + 1] = f[i] >= k ? nums[i] : -1; } return ans; }}class Solution {public: vector<int> resultsArray(vector<int> &nums, int k) { int n = nums.size(); int f[n]; f[0] = 1; for (int i = 1; i < n; ++i) { f[i] = nums[i] == nums[i - 1] + 1 ? f[i - 1] + 1 : 1; } vector<int> ans; for (int i = k - 1; i < n; ++i) { ans.push_back(f[i] >= k ? nums[i] : -1); } return ans; }};class Solution: def resultsArray(self, nums: List[int], k: int) -> List[int]: n = len(nums) f = [1] * n for i in range(1, n): if nums[i] == nums[i - 1] + 1: f[i] = f[i - 1] + 1 return [nums[i] if f[i] >= k else - 1 for i in range(k - 1, n)]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.