LeetCode 3254 - Find the Power of K-Size Subarrays I

LeetCode Problem 3254

Difficulty: 🟡 Medium
Topics: Array, Sliding Window

Solution

Problem Understanding

The problem asks us to examine every contiguous subarray of length k in the input array nums and determine its "power".

A subarray has valid power only if two conditions are simultaneously true:

1. The elements are sorted in strictly ascending order.
2. Every adjacent pair differs by exactly 1, meaning the sequence is consecutive.

If both conditions hold, the power is simply the maximum element of that subarray. Since the sequence is strictly ascending and consecutive, the maximum element is always the last element.

Otherwise, the power is -1.

For example, consider the subarray [2, 3, 4]:

• It is sorted in ascending order.
• Every pair differs by 1.

So its power is 4.

Now consider [3, 4, 3]:

• It is not sorted in ascending order.
• The consecutive property also fails.

So its power is -1.

The input consists of:

• nums, an integer array of length n
• k, the required subarray size

We must return an array of size n - k + 1, where each position contains the power of the corresponding window.

The constraints are relatively small:

• n <= 500

This means even an O(n * k) solution is completely acceptable because the worst case is only 500 * 500 = 250000 operations.

Still, there is a cleaner sliding window style solution that processes the array more efficiently in linear time.

Several edge cases are important:

• k = 1, every single element subarray is automatically consecutive and sorted, so the answer is simply the original array.
• Arrays with duplicate values, such as [2,2,2], fail because consecutive ascending numbers require differences of exactly 1.
• Descending arrays fail because the order requirement is violated.
• A sequence can be ascending but not consecutive, such as [1,3,5].
• A sequence can contain one invalid adjacent pair that invalidates the entire window.

Approaches

Brute Force

The most direct solution is to examine every subarray of size k.

For each window:

1. Check every adjacent pair.
2. Verify that:

• nums[i + 1] == nums[i] + 1

3. If all adjacent pairs satisfy the condition, return the last element of the window.
4. Otherwise, return -1.

This works because a strictly ascending consecutive sequence is fully characterized by adjacent differences of exactly 1.

The brute force method is straightforward and easy to reason about. However, for every window we repeatedly recheck many adjacent pairs that overlap with previous windows.

Since there are n - k + 1 windows and each requires up to k - 1 comparisons, the complexity is O(n * k).

Optimal Sliding Window Observation

The key observation is that validity depends only on adjacent pairs.

Define a pair as "good" if:

nums[i + 1] == nums[i] + 1

For a window of size k to be valid, all k - 1 adjacent pairs inside that window must be good.

Instead of rechecking the entire window each time, we can maintain the length of the current consecutive ascending streak.

If:

nums[i] == nums[i - 1] + 1

then we extend the streak.

Otherwise, we reset it.

Whenever the streak length becomes at least k, the current window ending at index i is valid, and its power is nums[i].

This transforms the solution into a linear scan.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * k)	O(1)	Checks every window independently
Optimal	O(n)	O(1)	Tracks consecutive ascending streak length

Algorithm Walkthrough

1. Initialize the result array with size n - k + 1, filled with -1.

We default every window to invalid. Only valid windows will be updated later. 2. Maintain a variable called streak.

streak represents the length of the current consecutive ascending sequence ending at the current index. 3. Start with streak = 1.

A single element always forms a valid streak of length 1. 4. Iterate through the array from left to right.

For each index i starting from 1:

• If nums[i] == nums[i - 1] + 1, extend the streak:

streak += 1

• Otherwise, reset:

streak = 1

5. Determine whether a valid window of size k ends at index i.

If:

streak >= k

then the subarray:

nums[i-k+1 : i+1]

is consecutive and ascending. 6. Store the power.

Since the window is ascending, the maximum value is the last element:

nums[i]

So:

result[i-k+1] = nums[i]

7. Handle the special case k == 1.

Every individual element is valid, so the answer is simply nums.

Why it works

The algorithm maintains the invariant that streak equals the length of the longest suffix ending at the current index that forms a consecutive ascending sequence.

A window of size k is valid exactly when this suffix length is at least k. Because every adjacent pair inside the window differs by 1, the window must be strictly ascending and consecutive.

Thus every valid window is detected exactly once, and every invalid window remains -1.

Python Solution

from typing import List

class Solution:
    def resultsArray(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)

        if k == 1:
            return nums[:]

        result = [-1] * (n - k + 1)

        streak = 1

        for i in range(1, n):
            if nums[i] == nums[i - 1] + 1:
                streak += 1
            else:
                streak = 1

            if streak >= k:
                result[i - k + 1] = nums[i]

        return result

The implementation begins by handling the special case where k == 1. Any single element subarray is trivially consecutive and ascending, so we return a copy of the original array.

Next, we create the result array initialized with -1. This automatically marks all windows invalid unless proven otherwise.

The streak variable tracks how many consecutive ascending elements currently extend to index i.

During iteration:

• If the current element continues the consecutive pattern, we increase streak.
• Otherwise, we reset it to 1.

Whenever streak >= k, we know the current window of size k ending at index i is valid. Since the sequence is ascending, the maximum element is the final element, nums[i].

The algorithm performs a single pass through the array and uses only constant extra memory.

Go Solution

func resultsArray(nums []int, k int) []int {
	n := len(nums)

	if k == 1 {
		result := make([]int, n)
		copy(result, nums)
		return result
	}

	result := make([]int, n-k+1)

	for i := range result {
		result[i] = -1
	}

	streak := 1

	for i := 1; i < n; i++ {
		if nums[i] == nums[i-1]+1 {
			streak++
		} else {
			streak = 1
		}

		if streak >= k {
			result[i-k+1] = nums[i]
		}
	}

	return result
}

The Go implementation follows the same logic as the Python solution.

One small difference is that Go slices are initialized with zero values, so we explicitly fill the result slice with -1.

For the k == 1 case, we create a copy of the input slice before returning it. This avoids returning the original underlying slice directly.

No integer overflow concerns exist because values remain well within Go's standard integer range.

Worked Examples

Example 1

Input:

nums = [1,2,3,4,3,2,5]
k = 3

We track the streak length while scanning.

i	nums[i]	Relation	streak	Valid Window?	result
1	2	2 = 1 + 1	2	No	[-1,-1,-1,-1,-1]
2	3	3 = 2 + 1	3	Yes	[3,-1,-1,-1,-1]
3	4	4 = 3 + 1	4	Yes	[3,4,-1,-1,-1]
4	3	Breaks	1	No	[3,4,-1,-1,-1]
5	2	Breaks	1	No	[3,4,-1,-1,-1]
6	5	Breaks	1	No	[3,4,-1,-1,-1]

Final answer:

[3,4,-1,-1,-1]

Example 2

Input:

nums = [2,2,2,2,2]
k = 4

i	nums[i]	Relation	streak	Valid Window?
1	2	Not consecutive	1	No
2	2	Not consecutive	1	No
3	2	Not consecutive	1	No
4	2	Not consecutive	1	No

No valid window ever appears.

Final answer:

[-1,-1]

Example 3

Input:

nums = [3,2,3,2,3,2]
k = 2

i	nums[i]	Relation	streak	result
1	2	Breaks	1	[-1,-1,-1,-1,-1]
2	3	3 = 2 + 1	2	[-1,3,-1,-1,-1]
3	2	Breaks	1	[-1,3,-1,-1,-1]
4	3	3 = 2 + 1	2	[-1,3,-1,3,-1]
5	2	Breaks	1	[-1,3,-1,3,-1]

Final answer:

[-1,3,-1,3,-1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the array
Space	O(1)	Only a few extra variables besides output

The algorithm scans the array exactly once. Every iteration performs only constant time operations, so the total runtime is linear in the size of the input.

The extra memory usage is constant because we only store the streak variable and loop counters. The output array does not count toward auxiliary space complexity.

Test Cases

from typing import List

class Solution:
    def resultsArray(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)

        if k == 1:
            return nums[:]

        result = [-1] * (n - k + 1)

        streak = 1

        for i in range(1, n):
            if nums[i] == nums[i - 1] + 1:
                streak += 1
            else:
                streak = 1

            if streak >= k:
                result[i - k + 1] = nums[i]

        return result

sol = Solution()

assert sol.resultsArray([1,2,3,4,3,2,5], 3) == [3,4,-1,-1,-1]  # provided example
assert sol.resultsArray([2,2,2,2,2], 4) == [-1,-1]  # duplicates break consecutiveness
assert sol.resultsArray([3,2,3,2,3,2], 2) == [-1,3,-1,3,-1]  # alternating valid pairs

assert sol.resultsArray([5], 1) == [5]  # single element array
assert sol.resultsArray([1,2,3,4], 1) == [1,2,3,4]  # k = 1 always valid
assert sol.resultsArray([1,2,3,4], 4) == [4]  # entire array valid
assert sol.resultsArray([4,3,2,1], 2) == [-1,-1,-1]  # descending order invalid
assert sol.resultsArray([1,3,5,7], 2) == [-1,-1,-1]  # ascending but not consecutive
assert sol.resultsArray([1,2,4,5,6], 3) == [-1,6,-1]  # only middle window valid
assert sol.resultsArray([10,11,12,13,14], 2) == [11,12,13,14]  # every window valid
assert sol.resultsArray([1,2,3,5,6,7], 3) == [3,-1,-1,7]  # two separate valid segments

Test Summary

Test	Why
[1,2,3,4,3,2,5], k=3	Standard mixed validity example
[2,2,2,2,2], k=4	Duplicate values invalidate windows
[3,2,3,2,3,2], k=2	Alternating valid and invalid windows
[5], k=1	Smallest possible input
[1,2,3,4], k=1	Every single element window is valid
[1,2,3,4], k=4	Entire array forms one valid window
[4,3,2,1], k=2	Descending sequences fail
[1,3,5,7], k=2	Ascending but non-consecutive values
[1,2,4,5,6], k=3	Partial validity inside array
[10,11,12,13,14], k=2	Every window valid
[1,2,3,5,6,7], k=3	Multiple separate valid streaks

Edge Cases

One important edge case occurs when k = 1. A single element is always trivially sorted and consecutive because there are no adjacent pairs to violate the conditions. A buggy implementation might incorrectly return -1 or fail to initialize the result properly. The solution handles this immediately by returning a copy of nums.

Another important case involves duplicate values such as [2,2,2]. Even though the values appear ordered, they are not strictly ascending and consecutive because the difference between adjacent values is 0 instead of 1. The implementation correctly rejects these windows because it explicitly checks for nums[i] == nums[i - 1] + 1.

Descending sequences such as [5,4,3] are another common source of mistakes. A naive implementation that only checks whether values differ by 1 without considering direction could accidentally accept them. The algorithm avoids this issue because it specifically requires the next value to equal the previous value plus one.

Another subtle case is ascending but non-consecutive sequences like [1,3,5]. These arrays are increasing, but gaps larger than 1 invalidate the window. Since the implementation checks exact equality with previous + 1, these windows are correctly marked invalid.