Find the Power of K-Size Subarrays I — Easy Problem & Solution

Problem statement

The power of a subarray is its maximum element if the subarray is sorted ascending and consecutive — each element exactly one more than the previous — and -1 otherwise.

Return the power of every contiguous subarray of length k, in order.

Example 1

Input: nums = [1,2,3,4,3,2,5], k = 3
Output: [3,4,-1,-1,-1]
Explanation: Only `[1,2,3]` and `[2,3,4]` run consecutively.

Example 2

Input: nums = [2,2,2,2,2], k = 4
Output: [-1,-1]
Explanation: Equal values are not consecutive.

Example 3

Input: nums = [3,2,3,2,3,2], k = 2
Output: [-1,3,-1,3,-1]

Constraints

• 1 <= n == nums.length <= 500
• 1 <= nums[i] <= 10^5
• 1 <= k <= n

How to solve Find the Power of K-Size Subarrays I

Check each window of length k for the "each element one more than the last" property; if it holds, the last element is the maximum.

Approach

1. Slide a window of length k across the array.
2. Verify nums[j] == nums[j-1] + 1 for every interior position.
3. Record nums[i + k - 1] when it holds, and -1 otherwise.

Why it works

The consecutive-and-increasing condition makes the last element the maximum for free — no scan for a max is needed. Keeping a running count of consecutive steps turns this into one linear pass, but at n <= 500 the direct check per window is already comfortable.

Complexity

• Time — O(n · k), or O(n) with a running count
• Space — O(n) for the output

Pitfalls

• Equal neighbours fail the test; the step must be exactly +1.
• The output has n - k + 1 entries, not n.
• With k == 1 every window trivially qualifies.

Reference solution

Python

from typing import List

def resultsArray(nums: List[int], k: int) -> List[int]:
    n = len(nums)
    out = []
    for i in range(n - k + 1):
        ok = all(nums[j] == nums[j - 1] + 1 for j in range(i + 1, i + k))
        out.append(nums[i + k - 1] if ok else -1)
    return out

JavaScript

var resultsArray = function(nums, k) {
    var n = nums.length;
    var out = [];
    for (var i = 0; i + k <= n; i++) {
        var ok = true;
        for (var j = i + 1; j < i + k; j++) {
            if (nums[j] !== nums[j - 1] + 1) { ok = false; break; }
        }
        out.push(ok ? nums[i + k - 1] : -1);
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy