Problem Description

You are given an array of integers nums of length n and a positive integer k.

The problem asks you to find the "power" of all subarrays of size k within the given array. The power of a subarray is defined as:

• The maximum element of the subarray if all elements in the subarray are consecutive integers sorted in ascending order
• -1 otherwise

A subarray has consecutive integers in ascending order when each element is exactly 1 more than the previous element. For example, [3, 4, 5] is consecutive and ascending, but [3, 5, 6] or [5, 4, 3] are not.

You need to check every possible subarray of size k in the array nums (sliding window approach), determine its power based on the rules above, and return an array results where:

• results[i] contains the power of the subarray nums[i...(i + k - 1)]
• The size of results will be n - k + 1 (the number of possible subarrays of size k)

For example, if nums = [1, 2, 3, 4, 5] and k = 3:

• Subarray [1, 2, 3]: consecutive and ascending → power = 3 (maximum element)
• Subarray [2, 3, 4]: consecutive and ascending → power = 4
• Subarray [3, 4, 5]: consecutive and ascending → power = 5
• Result: [3, 4, 5]

If nums = [1, 3, 4] and k = 2:

• Subarray [1, 3]: not consecutive → power = -1
• Subarray [3, 4]: consecutive and ascending → power = 4
• Result: [-1, 4]

Intuition

The key insight is that we don't need to check each subarray of size k independently. Instead, we can preprocess the array to identify consecutive ascending sequences efficiently.

Think about it this way: if we know that elements at positions i-2, i-1, and i form a consecutive ascending sequence, then we already have useful information about the subarray ending at position i. We don't need to recheck the entire subarray each time.

This leads us to track the length of consecutive ascending sequences ending at each position. We can create an array f where f[i] represents how many consecutive ascending elements there are ending at position i.

For example, if nums = [1, 2, 3, 5, 6, 7]:

• At index 0: f[0] = 1 (just the element 1 itself)
• At index 1: Since nums[1] = nums[0] + 1 (2 = 1 + 1), we have f[1] = f[0] + 1 = 2
• At index 2: Since nums[2] = nums[1] + 1 (3 = 2 + 1), we have f[2] = f[1] + 1 = 3
• At index 3: Since nums[3] ≠ nums[2] + 1 (5 ≠ 4), the sequence breaks, so f[3] = 1
• At index 4: Since nums[4] = nums[3] + 1 (6 = 5 + 1), we have f[4] = f[3] + 1 = 2
• At index 5: Since nums[5] = nums[4] + 1 (7 = 6 + 1), we have f[5] = f[4] + 1 = 3

Once we have this information, checking if a subarray of size k ending at position i is consecutive and ascending becomes trivial: we just need to check if f[i] >= k. If it is, then the last k elements form a valid consecutive ascending sequence, and the power is nums[i] (the maximum element, which is the last element in an ascending sequence). Otherwise, the power is -1.

This approach transforms a problem that could require checking k elements for each of the n - k + 1 subarrays (O(k × (n - k + 1)) time) into a simple linear scan with preprocessing (O(n) time).

Learn more about Sliding Window patterns.

Solution Approach

The solution implements the preprocessing approach using dynamic programming to track consecutive ascending sequences.

Step 1: Initialize the tracking array

We create an array f of size n where each element is initialized to 1. This represents that each element by itself forms a consecutive sequence of length 1.

f = [1] * n

Step 2: Build the consecutive sequence lengths

We iterate through the array starting from index 1, checking if each element forms a consecutive pair with its predecessor:

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

• If nums[i] = nums[i-1] + 1, then the current element extends the previous consecutive sequence, so f[i] = f[i-1] + 1
• Otherwise, f[i] remains 1 (the sequence breaks and starts fresh)

Step 3: Generate the results

For each possible subarray of size k, we check if it forms a valid consecutive ascending sequence:

return [nums[i] if f[i] >= k else -1 for i in range(k - 1, n)]

We iterate from index k-1 to n-1 (these are the ending positions of all possible subarrays of size k):

• If f[i] >= k, it means the subarray ending at position i has at least k consecutive ascending elements, so the power is nums[i] (the maximum element in the ascending sequence)
• Otherwise, the subarray doesn't form a valid consecutive sequence, so the power is -1

Time Complexity: O(n) - We make two passes through the array, both taking linear time.

Space Complexity: O(n) - We use an additional array f of size n to store the consecutive sequence lengths.

The elegance of this solution lies in how it transforms the problem from repeatedly checking subarrays to a simple preprocessing step followed by constant-time lookups for each subarray's validity.

Example Walkthrough

Let's walk through the solution with nums = [1, 2, 3, 5, 6, 7, 8] and k = 3.

Step 1: Initialize tracking array f

f = [1, 1, 1, 1, 1, 1, 1]

Each element starts with a consecutive sequence length of 1 (itself).

Step 2: Build consecutive sequence lengths

Starting from index 1, we check if each element is exactly 1 more than the previous:

• Index 1: nums[1] = 2 = nums[0] + 1 (2 = 1 + 1) ✓

  • f[1] = f[0] + 1 = 2

• Index 2: nums[2] = 3 = nums[1] + 1 (3 = 2 + 1) ✓

  • f[2] = f[1] + 1 = 3

• Index 3: nums[3] = 5 ≠ nums[2] + 1 (5 ≠ 4) ✗

  • f[3] remains 1 (sequence breaks)

• Index 4: nums[4] = 6 = nums[3] + 1 (6 = 5 + 1) ✓

  • f[4] = f[3] + 1 = 2

• Index 5: nums[5] = 7 = nums[4] + 1 (7 = 6 + 1) ✓

  • f[5] = f[4] + 1 = 3

• Index 6: nums[6] = 8 = nums[5] + 1 (8 = 7 + 1) ✓

  • f[6] = f[5] + 1 = 4

Final f array:

nums = [1, 2, 3, 5, 6, 7, 8]
f    = [1, 2, 3, 1, 2, 3, 4]

Step 3: Generate results for each subarray of size k=3

We check subarrays ending at indices 2 through 6:

• Index 2 (subarray [1, 2, 3]): f[2] = 3 >= 3 ✓

  • Power = nums[2] = 3

• Index 3 (subarray [2, 3, 5]): f[3] = 1 < 3 ✗

  • Power = -1

• Index 4 (subarray [3, 5, 6]): f[4] = 2 < 3 ✗

  • Power = -1

• Index 5 (subarray [5, 6, 7]): f[5] = 3 >= 3 ✓

  • Power = nums[5] = 7

• Index 6 (subarray [6, 7, 8]): f[6] = 4 >= 3 ✓

  • Power = nums[6] = 8

Final Result: [3, -1, -1, 7, 8]

The key insight: f[i] tells us immediately whether the subarray ending at position i has enough consecutive ascending elements. If f[i] >= k, we know the last k elements form a valid sequence without needing to check them individually.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n represents the length of the array nums. This is because the algorithm makes two linear passes through the array: one pass to build the array f that tracks consecutive sequences (iterating from index 1 to n-1), and another pass to construct the result array using list comprehension (iterating from index k-1 to n-1). Both operations are linear in terms of the input size.

The space complexity is O(n). The algorithm creates an auxiliary array f of size n to store the length of consecutive increasing sequences ending at each position. Additionally, the output array also requires O(n-k+1) space, which simplifies to O(n) in the worst case. Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding "Consecutive and Ascending"

The Mistake: Many developers initially interpret "consecutive integers in ascending order" as simply checking if the array is sorted in ascending order, without verifying that each element is exactly 1 more than the previous element.

Incorrect Implementation:

# WRONG: Only checks if sorted, not if consecutive
def is_valid_subarray(subarray):
    for i in range(1, len(subarray)):
        if subarray[i] <= subarray[i-1]:  # Only checks ascending
            return False
    return True

Why It Fails:

• Input: nums = [1, 3, 5, 7], k = 2
• Subarray [1, 3] would be considered valid (it's ascending)
• But it should return -1 because 3 is not consecutive to 1

Correct Approach:

# CORRECT: Checks both ascending AND consecutive (diff = 1)
def is_valid_subarray(subarray):
    for i in range(1, len(subarray)):
        if subarray[i] != subarray[i-1] + 1:  # Must be exactly +1
            return False
    return True

Pitfall 2: Off-by-One Errors in Index Calculation

The Mistake: Incorrectly calculating the starting or ending indices for the sliding window, especially when building the result array.

Incorrect Implementation:

# WRONG: Incorrect range for result generation
return [nums[i] if consecutive_length[i] >= k else -1 
        for i in range(k, n)]  # Should start at k-1, not k

Why It Fails:

• This would skip the first valid subarray and include an invalid index
• For nums = [1, 2, 3, 4], k = 2, it would check indices 2 and 3 instead of 1, 2, and 3

Correct Approach:

# CORRECT: Proper index range
return [nums[i] if consecutive_length[i] >= k else -1 
        for i in range(k - 1, n)]  # Start at k-1 (end of first k-length window)

Pitfall 3: Edge Case with k = 1

The Mistake: Not handling the special case where k = 1, assuming the algorithm needs modification for single-element subarrays.

Incorrect Assumption: Developers might add unnecessary special case handling:

# UNNECESSARY: Special case for k=1
if k == 1:
    return nums  # Every single element is "consecutive" with itself

Why the Original Solution Already Works: The preprocessing approach naturally handles k = 1:

• Every consecutive_length[i] starts at 1
• When checking consecutive_length[i] >= 1, it's always true
• Returns nums[i] for each position, which is correct

Pitfall 4: Confusion About Which Element to Return

The Mistake: Returning the wrong element from the valid consecutive subarray, such as the first element or middle element instead of the maximum (last) element.

Incorrect Implementation:

# WRONG: Returns the first element of the subarray
result = []
for i in range(k - 1, n):
    if consecutive_length[i] >= k:
        result.append(nums[i - k + 1])  # First element, not max
    else:
        result.append(-1)

Why It Fails:

• For subarray [3, 4, 5], it would return 3 instead of 5
• The problem specifically asks for the maximum element

Correct Approach:

# CORRECT: Returns the last (maximum) element
if consecutive_length[i] >= k:
    result.append(nums[i])  # Last element is the maximum in consecutive sequence

Prevention Tips:

1. Test with small examples: Walk through [1, 3, 4] with k = 2 manually
2. Verify boundary conditions: Check first and last subarrays explicitly
3. Understand the invariant: consecutive_length[i] represents the length of consecutive sequence ending at index i
4. Remember the property: In a consecutive ascending sequence, the last element is always the maximum