Find the Power of K-Size Subarrays I solution and explanation
Google
9 more videos on this problem
Find the Power of K-Size Subarrays I - Leetcode 3254 - PythonNeetCodeIO · 12:41 · 9K views
Find the Power of K-Size Subarrays I | Simple Explanation | Dry Run| Leetcode 3254 |codestorywithMIKcodestorywithMIK · 20:23 · 9K views
Find the Power of K Size Subarrays I | Leetcode 3254Techdose · 18:23 · 2K views
3254. Find the Power of K-Size Subarrays I | Monotonic Deque | Sliding Window | O(1) spaceAryan Mittal · 14:49 · 1K views
3254. Find the Power of K-Size Subarrays I (Leetcode Medium)Programming Live with Larry · 4:54 · 285 views
3254 Find the Power of K-Size Subarrays I | LeetCode Biweekly 137CodeInBits · 10:57 · 265 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
LeetCode 3254 - Find the Power of K-Sized Subarrays I - JavaAlpha-Code · 11:10 · 73 views
LEETCODE 3254 | Find the power of k-size subarrays i | leetcodeR Sai Siddhu · 9:05 · 69 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 <= 5001 <= nums[i] <= 1051 <= 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 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.
Approach 1: Brute Force Checking of 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.
def find_power_of_subarrays(nums, k):
n = len(nums)
results = [-1] * (n - k + 1)
for i in range(n - k + 1):
sorted_and_consecutive = True
max_element = nums[i]
for j in range(1, k):
if nums[i + j] < nums[i + j - 1] or nums[i + j] != nums[i + j - 1] + 1:
sorted_and_consecutive = False
break
if nums[i + j] > max_element:
max_element = nums[i + j]
if sorted_and_consecutive:
results[i] = max_element
return results
nums = [1, 2, 3, 4, 3, 2, 5]
k = 3
print(find_power_of_subarrays(nums, k))import java.util.Arrays;
public class SubarrayPower {
public static int[] findPowerOfSubarrays(int[] nums, int k) {
int n = nums.length;
int[] results = new int[n - k + 1];
Arrays.fill(results, -1);
for (int i = 0; i <= n - k; i++) {
boolean sortedAndConsecutive = true;
int maxElement = nums[i];
for (int j = 1; j < k; j++) {
if (nums[i + j] < nums[i + j - 1] || nums[i + j] != nums[i + j - 1] + 1) {
sortedAndConsecutive = false;
break;
}
if (nums[i + j] > maxElement) maxElement = nums[i + j];
}
if (sortedAndConsecutive)
results[i] = maxElement;
}
return results;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 3, 2, 5};
int k = 3;
int[] results = findPowerOfSubarrays(nums, k);
for (int result : results) {
System.out.print(result + " ");
}
}
}#include <iostream>
#include <vector>
bool isConsecutive(const std::vector<int>& nums, int start, int k) {
for (int i = 1; i < k; ++i) {
if (nums[start + i] != nums[start + i - 1] + 1) return false;
}
return true;
}
std::vector<int> findPowerOfSubarrays(const std::vector<int>& nums, int k) {
int n = nums.size();
std::vector<int> results(n - k + 1, -1);
for (int i = 0; i <= n - k; ++i) {
bool sortedAndConsecutive = true;
int maxElement = nums[i];
for (int j = 1; j < k; ++j) {
if (nums[i + j] < nums[i + j - 1] || nums[i + j] != nums[i + j - 1] + 1) {
sortedAndConsecutive = false;
break;
}
if (nums[i + j] > maxElement) maxElement = nums[i + j];
}
if (sortedAndConsecutive) results[i] = maxElement;
}
return results;
}
int main() {
std::vector<int> nums = {1, 2, 3, 4, 3, 2, 5};
int k = 3;
std::vector<int> results = findPowerOfSubarrays(nums, k);
for (int result : results) {
std::cout << result << " ";
}
return 0;
}function findPowerOfSubarrays(nums, k) {
const n = nums.length;
const results = new Array(n - k + 1).fill(-1);
for (let i = 0; i <= n - k; i++) {
let sortedAndConsecutive = true;
let maxElement = nums[i];
for (let j = 1; j < k; j++) {
if (nums[i + j] < nums[i + j - 1] || nums[i + j] !== nums[i + j - 1] + 1) {
sortedAndConsecutive = false;
break;
}
if (nums[i + j] > maxElement) maxElement = nums[i + j];
}
if (sortedAndConsecutive) results[i] = maxElement;
}
return results;
}
const nums = [1, 2, 3, 4, 3, 2, 5];
const k = 3;
console.log(findPowerOfSubarrays(nums, k));#include <stdio.h>
#include <stdbool.h>
bool isConsecutive(int *arr, int k) {
for (int i = 1; i < k; i++) {
if (arr[i] != arr[i-1] + 1) return false;
}
return true;
}
void findPowerOfSubarrays(int *nums, int n, int k, int *results) {
for (int i = 0; i <= n - k; i++) {
bool sortedAndConsecutive = true;
int maxElement = nums[i];
for (int j = i + 1; j < i + k; j++) {
if (nums[j] < nums[j - 1] || nums[j] != nums[j - 1] + 1) {
sortedAndConsecutive = false;
break;
}
if (nums[j] > maxElement) maxElement = nums[j];
}
results[i] = sortedAndConsecutive ? maxElement : -1;
}
}
int main() {
int nums[] = {1, 2, 3, 4, 3, 2, 5};
int k = 3;
int n = sizeof(nums) / sizeof(nums[0]);
int results[n - k + 1];
findPowerOfSubarrays(nums, n, k, results);
for (int i = 0; i < n - k + 1; i++) {
printf("%d ", results[i]);
}
return 0;
}using System;
public class SubarrayPower {
public static int[] FindPowerOfSubarrays(int[] nums, int k) {
int n = nums.Length;
int[] results = new int[n - k + 1];
Array.Fill(results, -1);
for (int i = 0; i <= n - k; i++) {
bool sortedAndConsecutive = true;
int maxElement = nums[i];
for (int j = 1; j < k; j++) {
if (nums[i + j] < nums[i + j - 1] || nums[i + j] != nums[i + j - 1] + 1) {
sortedAndConsecutive = false;
break;
}
if (nums[i + j] > maxElement) {
maxElement = nums[i + j];
}
}
if (sortedAndConsecutive) {
results[i] = maxElement;
}
}
return results;
}
public static void Main() {
int[] nums = {1, 2, 3, 4, 3, 2, 5};
int k = 3;
int[] results = FindPowerOfSubarrays(nums, k);
Console.WriteLine(string.Join(" ", results));
}
}In this Python solution, each subarray of length k is examined to ascertain the order and consecutiveness of elements, determining the power when conditions are met.
Time Complexity: O(n * k) for iterating over each subarray.
Space Complexity: O(n-k+1) for the results list.
Approach 2: Optimized Sliding Window Technique
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.
def find_power_with_sliding_window(nums, k):
n = len(nums)
results = [-1] * (n - k + 1)
for i in range(n - k + 1):
sorted_and_consecutive = True
for j in range(1, k):
if nums[i + j] != nums[i + j - 1] + 1:
sorted_and_consecutive = False
break
if sorted_and_consecutive:
results[i] = nums[i + k - 1]
return results
nums = [1, 2, 3, 4, 3, 2, 5]
k = 3
print(find_power_with_sliding_window(nums, k))public class SlidingWindow {
public static int[] findPowerWithSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] results = new int[n - k + 1];
for (int i = 0; i <= n - k; ++i) {
boolean isSortedAndConsecutive = true;
for (int j = 1; j < k; ++j) {
if (nums[i + j] != nums[i + j - 1] + 1) {
isSortedAndConsecutive = false;
break;
}
}
results[i] = isSortedAndConsecutive ? nums[i + k - 1] : -1;
}
return results;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 3, 2, 5};
int k = 3;
int[] results = findPowerWithSlidingWindow(nums, k);
for (int result : results) {
System.out.print(result + " ");
}
}
}#include <iostream>
#include <vector>
bool isConsecutiveAndSorted(const std::vector<int>& nums, int start, int k) {
for (int i = start + 1; i < start + k; ++i) {
if (nums[i] != nums[i - 1] + 1) return false;
}
return true;
}
std::vector<int> findPowerWithSlidingWindow(const std::vector<int>& nums, int k) {
int n = nums.size();
std::vector<int> results(n - k + 1, -1);
for (int i = 0; i <= n - k; ++i) {
if (isConsecutiveAndSorted(nums, i, k)) {
results[i] = nums[i + k - 1];
}
}
return results;
}
int main() {
std::vector<int> nums = {1, 2, 3, 4, 3, 2, 5};
int k = 3;
std::vector<int> results = findPowerWithSlidingWindow(nums, k);
for (int result : results) {
std::cout << result << " ";
}
return 0;
}function findPowerWithSlidingWindow(nums, k) {
const n = nums.length;
const results = new Array(n - k + 1).fill(-1);
for (let i = 0; i <= n - k; i++) {
let sortedAndConsecutive = true;
for (let j = 1; j < k; j++) {
if (nums[i + j] != nums[i + j - 1] + 1) {
sortedAndConsecutive = false;
break;
}
}
results[i] = sortedAndConsecutive ? nums[i + k - 1] : -1;
}
return results;
}
const nums = [1, 2, 3, 4, 3, 2, 5];
const k = 3;
console.log(findPowerWithSlidingWindow(nums, k));#include <stdio.h>
#include <stdbool.h>
bool isConsecutiveAndSorted(int *arr, int start, int k) {
for (int i = start + 1; i < start + k; i++) {
if (arr[i] != arr[i - 1] + 1) return false;
}
return true;
}
void findPowerWithSlidingWindow(int *nums, int n, int k, int *results) {
for (int i = 0; i <= n - k; i++) {
if (isConsecutiveAndSorted(nums, i, k)) {
int maxElem = nums[i + k - 1];
results[i] = maxElem;
} else {
results[i] = -1;
}
}
}
int main() {
int nums[] = {1, 2, 3, 4, 3, 2, 5};
int k = 3;
int n = sizeof(nums) / sizeof(nums[0]);
int results[n - k + 1];
findPowerWithSlidingWindow(nums, n, k, results);
for (int i = 0; i < n - k + 1; i++) {
printf("%d ", results[i]);
}
return 0;
}using System;
public class SlidingWindow {
public static int[] FindPowerWithSlidingWindow(int[] nums, int k) {
int n = nums.Length;
int[] results = new int[n - k + 1];
for (int i = 0; i <= n - k; i++) {
bool isSortedAndConsecutive = true;
for (int j = 1; j < k; j++) {
if (nums[i + j] != nums[i + j - 1] + 1) {
isSortedAndConsecutive = false;
break;
}
}
results[i] = isSortedAndConsecutive ? nums[i + k - 1] : -1;
}
return results;
}
public static void Main() {
int[] nums = {1, 2, 3, 4, 3, 2, 5};
int k = 3;
int[] results = FindPowerWithSlidingWindow(nums, k);
Console.WriteLine(string.Join(" ", results));
}
}This Python implementation uses sliding window techniques to evaluate each k-length period efficiently, determining power if orders are maintained.
Time Complexity: O(n * k) for checking sequential elements.
Space Complexity: O(n-k+1) for results.
Approach 3: 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
}Approach 4: Default Approach
export function resultsArray(nums: number[], k: number): number[] {
const n = nums.length;
const ans: number[] = [];
for (let i = 0, j = 0; i < n; i++) {
if (i && nums[i - 1] + 1 !== nums[i]) j = i;
if (i >= k - 1) {
ans.push(i - k + 1 < j ? -1 : nums[i]);
}
}
return ans;
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Checking of Subarrays | Time Complexity: |
| Optimized Sliding Window Technique | Time Complexity: |
| Recursion | – |
| Default Approach | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Find the Power of K-Size Subarrays I easy or hard?
Find the Power of K-Size Subarrays I is typically rated Medium difficulty. The brute force logic is straightforward, but recognizing that overlapping windows allow a linear-time sliding window optimization is the key step that raises the difficulty.
Find the Power of K-Size Subarrays I Python/Java solution
Python, Java, C++, and similar languages implement the same idea: iterate once through the array and maintain a counter for consecutive increments. When the streak length reaches k, record the last element as the power; otherwise store -1. The logic remains identical across languages with O(n) time complexity.
How to solve Find the Power of K-Size Subarrays I in O(n)?
Traverse the array while maintaining a counter for consecutive elements where nums[i] == nums[i-1] + 1. If the condition holds, increment the streak; otherwise reset it. Whenever the streak length is at least k, the subarray ending at index i forms a valid window and its power is nums[i]; otherwise record -1.
What is the best approach for Find the Power of K-Size Subarrays I?
The optimal approach uses a sliding window with a counter that tracks how long the current consecutive increasing streak lasts. When the streak length reaches at least k, the current window is valid and its power equals the last element. This reduces the runtime to O(n) while using O(1) extra space.
Is Find the Power of K-Size Subarrays I asked at Google/Amazon/Meta?
Problems involving sliding windows and consecutive sequence validation appear frequently in interviews at companies like Amazon, Google, and Meta. Variations often test your ability to reuse computations across overlapping subarrays to achieve O(n) performance.
What data structure is used in Find the Power of K-Size Subarrays I?
The solution primarily uses arrays and a sliding window traversal pattern. No additional complex data structures are required; a simple counter or index tracking consecutive increments is enough to compute valid windows efficiently.
What is the time complexity of Find the Power of K-Size Subarrays I?
The brute force method runs in O(n*k) time because each k-length window is checked independently. The optimized sliding window approach processes the array once and tracks consecutive increments, reducing the time complexity to O(n) with constant space.