Find the Power of K-Size Subarrays II solution and explanation
9 more videos on this problem
Find the Power of K-Size Subarrays II || LeetCode Biweekly Contest 137 || Leetcode Solutioncodi · 0:51 · 914 views
3254. Find the Power of K-Size Subarrays I | 3255. Find the Power of K-Size Subarrays II | MEDIUMcode Explainer · 12:13 · 466 views
3255. Find the Power of K-Size Subarrays II (Leetcode Medium)Programming Live with Larry · 6:04 · 464 views
LeetCode Biweekly Contest 137 | Find the Power of K-Size Subarrays IISmart Interviews · 16:57 · 340 views
3255. Find the Power of K-Size Subarrays IITech Courses · 9:52 · 230 views
3255 Find the Power of K-Size Subarrays II | LeetCode Biweekly 137CodeInBits · 11:27 · 125 views
Leetcode 3254 & 3255 | Find the Power of K-Size Subarrays I + II | Leetcode Biweekly Contest 137Road To FAANG · 11:27 · 125 views
3254 & 3255. Find the Power of K-Size Subarrays I & II | Prefix sum | Array | Brute force | LeetCodeLeet's Code · 20:03 · 102 views
3255. Find the Power of K-Size Subarrays II C++ Leetcode solutionCodeQuest · 13:00 · 73 views
Solved LeetCode Problem 3255 || Find the Power of K-Size Subarrays IIDev Dive · 7:48 · 60 views
The problem
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
Approach overview
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.
Approach 1: Sliding Window with HashSet
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.
def find_power(nums, k):
n = len(nums)
results = []
for i in range(n - k + 1):
subarray = nums[i:i + k]
if len(set(subarray)) == k and max(subarray) - min(subarray) == k - 1:
results.append(max(subarray))
else:
results.append(-1)
return resultsThe 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.
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.
Approach 2: Optimized with Sorting
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.
def find_power_optimized(nums, k):
n = len(nums)
results = []
for i in range(n - k + 1):
subarray = nums[i:i + k]
sorted_subarray = sorted(subarray)
if all(sorted_subarray[j+1] - sorted_subarray[j] == 1 for j in range(k - 1)):
results.append(sorted_subarray[-1])
else:
results.append(-1)
return resultsThe function leverages sorting within each k-length subarray to easily check if numbers are consecutive. This reduces the complexity involved in each check.
The time complexity is O(n * k log k) due to sorting each subarray. The space complexity remains O(k) for temporary storage.
Approach 3: Sliding Window with Sorting Verification
In this approach, we utilize a sliding window technique to traverse through subarrays of size k. For each subarray, we perform the following steps:
- Extract the subarray of size k.
- Check whether the elements of the subarray are both consecutive and sorted in ascending order. This involves ensuring that the difference between consecutive elements is 1 and the elements are in increasing order.
- If both conditions are satisfied, find the maximum element of the subarray and append it to the result. Otherwise, append -1.
The sliding window allows us to efficiently move through the array and avoid recomputation for the overlapping parts of the subarrays.
def find_power(nums, k):
n = len(nums)
result = [-1] * (n - k + 1)
for i in range(n - k + 1):
is_consecutive_sorted = all(nums[j + 1] - nums[j] == 1 for j in range(i, i + k - 1))
if is_consecutive_sorted:
result[i] = max(nums[i:i + k])
return result
# Example use case
def main():
nums = [1, 2, 3, 4, 3, 2, 5]
k = 3
print(find_power(nums, k))
main()import java.util.Arrays;
public class SubarrayPower {
public static int[] findPower(int[] nums, int k) {
int n = nums.length;
int[] result = new int[n - k + 1];
for (int i = 0; i <= n - k; i++) {
boolean isValid = true;
for (int j = i; j < i + k - 1; j++) {
if (nums[j + 1] - nums[j] != 1) {
isValid = false;
break;
}
}
if (isValid) {
result[i] = Arrays.stream(nums, i, i + k).max().orElse(-1);
} else {
result[i] = -1;
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 3, 2, 5};
int k = 3;
int[] results = findPower(nums, k);
for (int res : results) {
System.out.print(res + " ");
}
}
}#include <vector>
#include <iostream>
#include <algorithm>
std::vector<int> findPower(std::vector<int>& nums, int k) {
std::vector<int> result(nums.size() - k + 1, -1);
for (size_t i = 0; i <= nums.size() - k; ++i) {
bool isValid = true;
for (int j = i; j < i + k - 1; ++j) {
if (nums[j + 1] - nums[j] != 1) {
isValid = false;
break;
}
}
if (isValid) {
result[i] = *std::max_element(nums.begin() + i, nums.begin() + i + k);
}
}
return result;
}
int main() {
std::vector<int> nums = {1, 2, 3, 4, 3, 2, 5};
int k = 3;
std::vector<int> result = findPower(nums, k);
for (int power : result) {
std::cout << power << " ";
}
return 0;
}function findPower(nums, k) {
const result = new Array(nums.length - k + 1).fill(-1);
for (let i = 0; i <= nums.length - k; i++) {
let valid = true;
for (let j = i; j < i + k - 1; j++) {
if (nums[j + 1] - nums[j] !== 1) {
valid = false;
break;
}
}
if (valid) {
result[i] = Math.max(...nums.slice(i, i + k));
}
}
return result;
}
// Example usage
const nums = [1, 2, 3, 4, 3, 2, 5];
const k = 3;
console.log(findPower(nums, k));#include <stdio.h>
#include <stdlib.h>
int* findPower(int* nums, int numsSize, int k, int* returnSize) {
*returnSize = numsSize - k + 1;
int* result = (int*)malloc((*returnSize) * sizeof(int));
for (int i = 0; i <= numsSize - k; ++i) {
int isConsecutiveAndSorted = 1;
for (int j = i; j < i + k - 1; ++j) {
if (nums[j + 1] - nums[j] != 1) {
isConsecutiveAndSorted = 0;
break;
}
}
if (isConsecutiveAndSorted) {
int max = nums[i];
for (int j = i + 1; j < i + k; ++j) {
if (nums[j] > max) {
max = nums[j];
}
}
result[i] = max;
} else {
result[i] = -1;
}
}
return result;
}
int main() {
int nums[] = {1, 2, 3, 4, 3, 2, 5};
int k = 3;
int returnSize;
int* results = findPower(nums, sizeof(nums) / sizeof(nums[0]), k, &returnSize);
for (int i = 0; i < returnSize; ++i) {
printf("%d ", results[i]);
}
free(results);
return 0;
}using System;
using System.Linq;
class Program {
public static int[] FindPower(int[] nums, int k) {
int n = nums.Length;
int[] result = new int[n - k + 1];
for (int i = 0; i <= n - k; i++) {
bool isValid = true;
for (int j = i; j < i + k - 1; j++) {
if (nums[j + 1] - nums[j] != 1) {
isValid = false;
break;
}
}
result[i] = isValid ? nums.Skip(i).Take(k).Max() : -1;
}
return result;
}
static void Main() {
int[] nums = { 1, 2, 3, 4, 3, 2, 5 };
int k = 3;
int[] results = FindPower(nums, k);
Console.WriteLine(string.Join(" ", results));
}
}This Python function implements sliding window checks for all elements being consecutive and sorted within each window before deciding whether to calculate the maximum element of the current subarray.
- Time complexity: O(n * k).
- Space complexity: O(n - k + 1).
Approach 4: Optimized Sliding Window with Cache
In this approach, we optimize the sliding window by caching information at each step:
- Track the required max element of the subarray if consecutive and sorted.
- Use a difference array or prefix sums to track differences between the elements in successive calls.
- Update only the necessary information as the window slides by using queues or heaps when applicable, hence reducing redundant calculations.
This reduces unnecessary calculations by leveraging computational history effectively.
def find_power_optimized(nums, k):
n = len(nums)
result = [-1] * (n - k + 1)
for i in range(n - k + 1):
is_consecutive_sorted = all(nums[j + 1] - nums[j] == 1 for j in range(i, i + k - 1))
if is_consecutive_sorted:
result[i] = max(nums[i:i + k])
return result
# Example use case
def main():
nums = [1, 2, 3, 4, 3, 2, 5]
k = 3
print(find_power_optimized(nums, k))
main()import java.util.Arrays;
public class SubarrayPower {
public static int[] findPowerOptimized(int[] nums, int k) {
int n = nums.length;
int[] result = new int[n - k + 1];
for (int i = 0; i <= n - k; i++) {
boolean isValid = true;
for (int j = i; j < i + k - 1; j++) {
if (nums[j + 1] - nums[j] != 1) {
isValid = false;
break;
}
}
if (isValid) {
result[i] = Arrays.stream(nums, i, i + k).max().orElse(-1);
} else {
result[i] = -1;
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 3, 2, 5};
int k = 3;
int[] results = findPowerOptimized(nums, k);
for (int res : results) {
System.out.print(res + " ");
}
}
}#include <vector>
#include <iostream>
std::vector<int> findPowerOptimized(std::vector<int>& nums, int k) {
std::vector<int> result(nums.size() - k + 1, -1);
for (size_t i = 0; i <= nums.size() - k; ++i) {
bool isValid = true;
for (int j = i; j < i + k - 1; ++j) {
if (nums[j + 1] - nums[j] != 1) {
isValid = false;
break;
}
}
if (isValid) {
result[i] = *std::max_element(nums.begin() + i, nums.begin() + i + k);
}
}
return result;
}
int main() {
std::vector<int> nums = {1, 2, 3, 4, 3, 2, 5};
int k = 3;
std::vector<int> result = findPowerOptimized(nums, k);
for (int power : result) {
std::cout << power << " ";
}
return 0;
}function findPowerOptimized(nums, k) {
const result = new Array(nums.length - k + 1).fill(-1);
const n = nums.length;
for (let i = 0; i <= n - k; i++) {
let valid = true;
for (let j = i; j < i + k - 1; j++) {
if (nums[j + 1] - nums[j] !== 1) {
valid = false;
break;
}
}
if (valid) {
result[i] = Math.max(...nums.slice(i, i + k));
}
}
return result;
}
// Example usage
const nums = [1, 2, 3, 4, 3, 2, 5];
const k = 3;
console.log(findPowerOptimized(nums, k));#include <stdio.h>
#include <stdlib.h>
int* findPowerOptimized(int* nums, int numsSize, int k, int* returnSize) {
*returnSize = numsSize - k + 1;
int* result = (int*)malloc((*returnSize) * sizeof(int));
for (int i = 0; i <= numsSize - k; ++i) {
int isConsecutive = 1;
for (int j = i; j < i + k - 1; ++j) {
if (nums[j + 1] - nums[j] != 1) {
isConsecutive = 0;
break;
}
}
if (isConsecutive) {
int max = nums[i];
for (int j = i + 1; j < i + k; ++j) {
if (nums[j] > max) {
max = nums[j];
}
}
result[i] = max;
} else {
result[i] = -1;
}
}
return result;
}
int main() {
int nums[] = {1, 2, 3, 4, 3, 2, 5};
int k = 3;
int returnSize;
int* results = findPowerOptimized(nums, sizeof(nums) / sizeof(nums[0]), k, &returnSize);
for (int i = 0; i < returnSize; ++i) {
printf("%d ", results[i]);
}
free(results);
return 0;
}using System;
using System.Linq;
class Program {
public static int[] FindPowerOptimized(int[] nums, int k) {
int n = nums.Length;
int[] result = new int[n - k + 1];
for (int i = 0; i <= n - k; i++) {
bool isValid = true;
for (int j = i; j < i + k - 1; j++) {
if (nums[j + 1] - nums[j] != 1) {
isValid = false;
break;
}
}
result[i] = isValid ? nums.Skip(i).Take(k).Max() : -1;
}
return result;
}
static void Main() {
int[] nums = { 1, 2, 3, 4, 3, 2, 5 };
int k = 3;
int[] results = FindPowerOptimized(nums, k);
Console.WriteLine(string.Join(" ", results));
}
}The Python function retains optimized techniques such as reusing computations where valid, though improvements are contingent on underlying library efficiencies in iteration and memory access.
- Time complexity: Ideally O(n) with optimizations.
- Space complexity: O(n - k + 1) with minimal overhead due to computation pathways.
Approach 5: Recursion
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.
function resultsArray(nums: number[], k: number): number[] {
const n = nums.length;
const f: number[] = Array(n).fill(1);
for (let i = 1; i < n; ++i) {
if (nums[i] === nums[i - 1] + 1) {
f[i] = f[i - 1] + 1;
}
}
const ans: number[] = [];
for (let i = k - 1; i < n; ++i) {
ans.push(f[i] >= k ? nums[i] : -1);
}
return ans;
}func resultsArray(nums []int, k int) (ans []int) {
n := len(nums)
f := make([]int, n)
f[0] = 1
for i := 1; i < n; i++ {
if nums[i] == nums[i-1]+1 {
f[i] = f[i-1] + 1
} else {
f[i] = 1
}
}
for i := k - 1; i < n; i++ {
if f[i] >= k {
ans = append(ans, nums[i])
} else {
ans = append(ans, -1)
}
}
return
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Find the Power of K-Size Subarrays II easy or hard?
Find the Power of K-Size Subarrays II is classified as Medium difficulty on LeetCode with an acceptance rate around 31%. The challenge is recognizing that consecutive windows share structure and can be validated incrementally instead of recomputing properties for every subarray.
Find the Power of K-Size Subarrays II Python/Java solution
Most implementations iterate through the array once while maintaining window state. Python, Java, C++, C#, and JavaScript solutions typically implement the O(n) sliding window method, returning nums[i] when a valid consecutive window of size k is detected and -1 otherwise.
How to solve Find the Power of K-Size Subarrays II in O(n)?
Use a sliding window that tracks consecutive increments between adjacent elements. If nums[i] + 1 == nums[i+1], extend the current streak; otherwise reset it. When the streak length reaches at least k, the window ending at that index contains k consecutive integers and the answer for that window is the maximum element, nums[i].
What is the best approach for Find the Power of K-Size Subarrays II?
The most efficient approach uses a sliding window with cached consecutive checks. Instead of re-evaluating each k-length subarray, track whether nums[i] + 1 == nums[i+1] as you move the window. When a streak of length k is maintained, the window forms consecutive integers and its power equals the last element. This achieves O(n) time and O(1) extra space.
Is Find the Power of K-Size Subarrays II asked at Google/Amazon/Meta?
Problems involving sliding window validation and consecutive sequence detection appear frequently in interviews at companies like Amazon, Google, and Meta. Variations of this question test window invariants, incremental updates, and efficient array traversal.
What data structure is used in Find the Power of K-Size Subarrays II?
Common implementations use arrays with the sliding window technique. Some baseline solutions also use a HashSet to check uniqueness or sorting to verify consecutive order. The optimal solution avoids extra structures and relies on simple counters while scanning the array.
What is the time complexity of Find the Power of K-Size Subarrays II?
Time complexity ranges from O(n * k log k) for approaches that sort each window to O(n) for the optimized sliding window method. The linear solution works by maintaining a running count of consecutive relationships rather than recomputing them for every window.