LeetCode 3255 - Find the Power of K-Size Subarrays II

LeetCode Problem 3255

Difficulty: 🟡 Medium
Topics: Array, Sliding Window

Solution

Problem Understanding

The problem asks us to evaluate every contiguous subarray of length k in the given array nums.

For each subarray, we must determine whether it satisfies two conditions simultaneously:

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

If both conditions are true, then the power of that subarray is its maximum element. Since the array is strictly increasing and consecutive, the maximum element is simply the last element of the subarray.

If either condition fails, the power is -1.

We must return an array where each position corresponds to the power of one length-k subarray.

For example, suppose:

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

The subarray [1,2,3] is strictly increasing and consecutive, so its power is 3.

The subarray [3,4,3] fails because the sequence stops increasing, so its power is -1.

The constraints are important:

• n can be as large as 10^5
• A naive solution that checks every subarray element-by-element would be too slow
• We need something close to linear time

The problem guarantees:

• k is always valid
• All numbers are positive integers
• The array length is at least 1

Several edge cases are important:

• k = 1, every single element is trivially consecutive and sorted
• Arrays with repeated values
• Arrays that are increasing but not consecutive, such as [1,3,5]
• Arrays that are consecutive but decreasing, such as [5,4,3]
• Very large arrays where quadratic approaches will time out

Approaches

Brute Force Approach

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

For each starting position:

1. Extract the window of length k
2. Check every adjacent pair
3. Verify:

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

4. If all checks pass, store the last element
5. Otherwise store -1

This approach is correct because it explicitly validates the definition of a valid subarray.

However, there are n - k + 1 windows, and each window requires up to k - 1 comparisons.

That leads to:

O((n - k + 1) * k)

In the worst case, this becomes O(nk), which is too slow when both n and k are large.

Optimal Sliding Window Observation

The key observation is that a valid subarray requires every adjacent pair inside the window to satisfy:

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

Instead of rechecking the entire window repeatedly, we can track the length of the current consecutive increasing streak.

Suppose we process the array from left to right.

If:

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

then the streak continues.

Otherwise, the streak resets to length 1.

Now consider a window ending at index i.

If the current streak length is at least k, then the last k elements form a valid subarray.

Since the subarray is strictly increasing and consecutive, its maximum element is simply nums[i].

This allows us to solve the problem in linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(nk)	O(1)	Checks every window independently
Optimal	O(n)	O(1)	Tracks consecutive streak length while scanning once

Algorithm Walkthrough

1. Initialize the result array.

The final answer contains n - k + 1 values, one for each window. 2. Handle the special case where k == 1.

Any single element is trivially sorted and consecutive, so the answer is simply the original array. 3. Maintain a variable called streak.

This variable stores the length of the current consecutive increasing sequence ending at the current index. 4. Start scanning from index 0.

Initially, the streak length is 1 because a single element always forms a valid streak. 5. For each index i > 0, compare nums[i] with nums[i-1].

If:

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

then the consecutive sequence continues, so increment streak.

Otherwise, reset streak = 1. 6. Once we reach an index where a full window exists, determine whether it is valid.

A window of size k ending at index i is valid if:

streak >= k

because that means the last k elements are consecutive and strictly increasing. 7. Store the answer for that window.

• If valid, append nums[i]
• Otherwise append -1

8. Continue until the entire array has been processed.

Why it works

The algorithm maintains the invariant that streak equals the length of the longest valid consecutive increasing suffix ending at the current index.

If streak >= k, then the last k elements necessarily satisfy:

nums[j+1] == nums[j] + 1

for every adjacent pair in the window.

That exactly matches the problem definition, so the window is valid. If the streak is smaller than k, then at least one adjacent pair inside the window violates the condition, making the window invalid.

Because every window is evaluated correctly using this invariant, the algorithm is correct.

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[:]

        results = []
        streak = 1

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

            if i >= k - 1:
                if streak >= k:
                    results.append(nums[i])
                else:
                    results.append(-1)

        return results

The implementation closely follows the algorithm described earlier.

The first step handles the special case where k == 1. Since every single element automatically satisfies the conditions, we can immediately return a copy of the array.

The variable streak tracks the length of the current consecutive increasing sequence ending at the current index.

During iteration:

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

determines whether the streak continues.

If the condition is true, we extend the streak. Otherwise, we reset it to 1.

Once i >= k - 1, a complete window of size k exists. At that point:

• streak >= k means the window is valid
• otherwise the window is invalid

For valid windows, the maximum element is the final element, nums[i].

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, 0, n-k+1)
	streak := 1

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

		if i >= k-1 {
			if streak >= k {
				result = append(result, nums[i])
			} else {
				result = append(result, -1)
			}
		}
	}

	return result
}

The Go implementation mirrors the Python logic almost exactly.

One small difference is that Go slices require explicit allocation. The result slice is initialized with capacity n-k+1 to reduce reallocations.

The special case for k == 1 returns a copied slice rather than the original slice. This avoids unintended side effects if the caller later modifies the returned slice.

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

Worked Examples

Example 1

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

We track the streak length at each position.

i	nums[i]	Consecutive with previous?	streak	Window Exists?	Result
0	1	N/A	1	No
1	2	Yes	2	No
2	3	Yes	3	Yes	3
3	4	Yes	4	Yes	4
4	3	No	1	Yes	-1
5	2	No	1	Yes	-1
6	5	No	1	Yes	-1

Final output:

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

Example 2

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

No adjacent pair differs by exactly 1.

i	nums[i]	Consecutive?	streak	Result
0	2	N/A	1
1	2	No	1
2	2	No	1
3	2	No	1	-1
4	2	No	1	-1

Final output:

[-1,-1]

Example 3

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

i	nums[i]	Consecutive?	streak	Result
0	3	N/A	1
1	2	No	1	-1
2	3	Yes	2	3
3	2	No	1	-1
4	3	Yes	2	3
5	2	No	1	-1

Final output:

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

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed exactly once
Space	O(1)	Only a few extra variables are used, excluding output

The algorithm performs a single left-to-right scan of the array. Each iteration does constant work, so the total runtime is linear.

The only auxiliary memory used is the streak variable and a few loop variables. The output array itself is not counted 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[:]

        results = []
        streak = 1

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

            if i >= k - 1:
                if streak >= k:
                    results.append(nums[i])
                else:
                    results.append(-1)

        return results

sol = Solution()

assert sol.resultsArray([1,2,3,4,3,2,5], 3) == [3,4,-1,-1,-1]  # official example
assert sol.resultsArray([2,2,2,2,2], 4) == [-1,-1]  # repeated values
assert sol.resultsArray([3,2,3,2,3,2], 2) == [-1,3,-1,3,-1]  # alternating valid windows

assert sol.resultsArray([1], 1) == [1]  # single element array
assert sol.resultsArray([5,6,7,8], 1) == [5,6,7,8]  # k = 1 always valid
assert sol.resultsArray([1,2,3,4], 4) == [4]  # entire array valid
assert sol.resultsArray([4,3,2,1], 4) == [-1]  # decreasing array
assert sol.resultsArray([1,3,5,7], 2) == [-1,-1,-1]  # increasing but not consecutive
assert sol.resultsArray([10,11,12,13,14], 3) == [12,13,14]  # all windows valid
assert sol.resultsArray([1,2,4,5,6], 3) == [-1,6]  # streak reset then recovery
assert sol.resultsArray([7,8], 2) == [8]  # smallest valid window
assert sol.resultsArray([7,9], 2) == [-1]  # smallest invalid window

Test Summary

Test	Why
[1,2,3,4,3,2,5], k=3	Verifies mixed valid and invalid windows
[2,2,2,2,2], k=4	Checks repeated values
[3,2,3,2,3,2], k=2	Tests alternating validity
[1], k=1	Smallest possible input
[5,6,7,8], k=1	Ensures all single-element windows succeed
[1,2,3,4], k=4	Entire array forms one valid window
[4,3,2,1], k=4	Strictly decreasing sequence
[1,3,5,7], k=2	Increasing but non-consecutive values
[10,11,12,13,14], k=3	Every window valid
[1,2,4,5,6], k=3	Tests streak reset behavior
[7,8], k=2	Smallest valid size-2 window
[7,9], k=2	Smallest invalid size-2 window

Edge Cases

One important edge case is when k = 1. A single element is always trivially sorted and consecutive because there are no adjacent pairs that can violate the conditions. A common mistake is to run the normal sliding-window logic unnecessarily or incorrectly reject such windows. The implementation handles this immediately by returning a copy of the original array.

Another important case is repeated values such as [2,2,2,2]. Even though the values are close together, consecutive integers require a difference of exactly 1. Equal neighboring values must invalidate the streak. The condition:

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

correctly rejects duplicates.

A third important edge case is sequences that are increasing but not consecutive, such as [1,3,5,7]. A naive implementation that only checks sorted order would incorrectly accept these windows. The algorithm specifically requires adjacent values to differ by exactly 1, ensuring such cases are rejected.

Another subtle case is when a valid streak breaks and later resumes, such as [1,2,4,5,6]. After encountering 4, the previous streak becomes invalid and must reset. The implementation correctly resets streak = 1, allowing future windows like [4,5,6] to still be recognized as valid.