Skip to main content
Talentd

Find the Power of K-Size Subarrays II - Solution & Explanation

MediumArraySliding Window21 min read
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums[i] <= 106
  • 1 <= 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.

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.

Code

Python

Python

Complexity

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.

Try this approach in the editor →

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.

The function leverages sorting within each k-length subarray to easily check if numbers are consecutive. This reduces the complexity involved in each check.

Code

Python

Python

Complexity

The time complexity is O(n * k log k) due to sorting each subarray. The space complexity remains O(k) for temporary storage.

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

  • Time complexity: O(n * k), where n is the length of the array, and k is the subarray size.
  • Space complexity: O(n - k + 1), for storing the results.
Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

  • Time complexity: O(n) in idealized form but often O(n * k) if optimizations can't bypass the iteration for checks.
  • Space complexity: O(n - k + 1).
Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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
  • Time complexity: O(n * k), where n is the length of the array, and k is the subarray size.
  • Space complexity: O(n - k + 1), for storing the results.
Optimized Sliding Window with Cache
  • Time complexity: O(n) in idealized form but often O(n * k) if optimizations can't bypass the iteration for checks.
  • Space complexity: O(n - k + 1).
Recursion—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sliding Window with HashSetO(n * k)O(k)Simple correctness check for uniqueness and range
Sorting Each WindowO(n * k log k)O(k)When implementation simplicity is preferred
Sliding Window with Sorting VerificationO(n * k log k)O(k)Cross-language approach relying on built-in sorting
Optimized Sliding Window with CacheO(n)O(1)Best choice for large arrays and interview settings

Video Solution

Find the Power of K-Size Subarrays II || LeetCode Biweekly Contest 137 || Leetcode Solution • codi • 914 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Find the Power of K-Size Subarrays II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Sum of Distinct Subarrays With Length K