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 in the given array. The power of an array is defined with specific rules:

• If all elements in the subarray are consecutive and sorted in ascending order, the power equals the maximum element (which would be the last element in this case)
• Otherwise, the power is -1

For an array to have consecutive and sorted elements in ascending order, each element must be exactly 1 greater than the previous element. For example, [3, 4, 5] is consecutive and sorted, but [3, 5, 6] is not consecutive (missing 4), and [5, 4, 3] is not sorted in ascending order.

You need to examine every subarray of size k in the array nums. Starting from index 0, check the subarray nums[0..k-1], then nums[1..k], then nums[2..k+1], and so on, until you reach the last possible subarray nums[n-k..n-1].

The output should be an array results of size n - k + 1, where results[i] contains the power of the subarray starting at index i and having length k.

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

• Subarray [1, 2, 3]: consecutive and sorted → power = 3
• Subarray [2, 3, 4]: consecutive and sorted → power = 4
• Subarray [3, 4, 3]: not consecutive/sorted → power = -1
• Subarray [4, 3, 2]: not sorted in ascending order → power = -1
• Subarray [3, 2, 5]: not consecutive → power = -1

The result would be [3, 4, -1, -1, -1].

Intuition

The key insight is that we don't need to check each subarray of size k independently. Instead, we can precompute information about consecutive increasing sequences throughout the entire array.

Think about what makes a subarray valid: every element must be exactly 1 greater than the previous element. If we know how many consecutive increasing elements end at each position, we can quickly determine if a subarray of size k is valid.

Consider this observation: if we're at position i and we know that there are at least k consecutive increasing elements ending at position i, then the subarray ending at position i with length k must be valid. For example, if at index 5 we have 4 consecutive increasing elements ending there (like [3, 4, 5, 6]), then any subarray of size 3 or less ending at index 5 would be valid.

This leads us to create an auxiliary array f where f[i] represents the length of the consecutive increasing sequence ending at index i. We can build this array in a single pass:

• Start with f[0] = 1 (every element forms a sequence of length 1 by itself)
• For each subsequent position i, check if nums[i] = nums[i-1] + 1
  • If yes, then f[i] = f[i-1] + 1 (extending the previous sequence)
  • If no, then f[i] = 1 (starting a new sequence)

Once we have the f array, checking if a subarray of size k ending at position i is valid becomes trivial: just check if f[i] >= k. If it is, the power is nums[i] (the maximum element in that consecutive sequence); otherwise, it's -1.

This approach transforms a problem that seems to require checking each subarray individually (which would involve nested loops) into a problem solvable with two simple linear passes through the array.

Learn more about Sliding Window patterns.

Solution Approach

The solution implements the precomputation strategy using dynamic programming principles:

Step 1: Initialize the consecutive sequence length array

Create an array f of size n where each element is initialized to 1. This represents that every element forms at least a sequence of length 1 by itself.

f = [1] * n

Step 2: Build the consecutive sequence information

Traverse the array from index 1 to n-1. For each position i, check if the current element forms a consecutive sequence with the previous element:

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, it means the current element continues the consecutive increasing sequence from the previous position, so we set f[i] = f[i-1] + 1
• Otherwise, f[i] remains 1, indicating a new sequence starts at this position

Step 3: Generate the results

For each possible subarray of size k, we check the ending position to determine the power:

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)
• For each ending position i, if f[i] >= k, it means there are at least k consecutive increasing elements ending at position i, making the subarray valid
  • The power is nums[i] (the maximum element in the consecutive sequence)
• If f[i] < k, the subarray is not valid, so the power is -1

Time Complexity: O(n) - We make two linear passes through the array
Space Complexity: O(n) - We use an additional array f of size n to store the consecutive sequence lengths

This approach efficiently solves the problem by transforming it from checking each subarray individually to a simple lookup operation after preprocessing.

Example Walkthrough

Let's walk through a concrete example with nums = [1, 2, 3, 1, 2] and k = 3.

Step 1: Build the consecutive sequence length array f

We initialize f = [1, 1, 1, 1, 1] (every element starts as a sequence of length 1).

Now we traverse from index 1 to 4:

• At index 1: nums[1] = 2 and nums[0] = 1. Since 2 = 1 + 1, we have consecutive elements.
  Update: f[1] = f[0] + 1 = 1 + 1 = 2
  Result: f = [1, 2, 1, 1, 1]

• At index 2: nums[2] = 3 and nums[1] = 2. Since 3 = 2 + 1, consecutive!
  Update: f[2] = f[1] + 1 = 2 + 1 = 3
  Result: f = [1, 2, 3, 1, 1]

• At index 3: nums[3] = 1 and nums[2] = 3. Since 1 ≠ 3 + 1, not consecutive.
  No update needed (remains 1).
  Result: f = [1, 2, 3, 1, 1]

• At index 4: nums[4] = 2 and nums[3] = 1. Since 2 = 1 + 1, consecutive!
  Update: f[4] = f[3] + 1 = 1 + 1 = 2
  Final: f = [1, 2, 3, 1, 2]

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

We check subarrays ending at indices 2, 3, and 4:

• Subarray [1, 2, 3] ends at index 2:
  Check: f[2] = 3 >= k = 3? Yes!
  Power = nums[2] = 3

• Subarray [2, 3, 1] ends at index 3:
  Check: f[3] = 1 >= k = 3? No.
  Power = -1

• Subarray [3, 1, 2] ends at index 4:
  Check: f[4] = 2 >= k = 3? No.
  Power = -1

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

The key insight: we only needed to check the value at the ending position of each subarray in our precomputed f array, rather than examining all elements within each subarray. The f array tells us exactly how many consecutive increasing elements end at each position, making the validation instant.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n represents the length of the array nums. The algorithm iterates through the array once to build the f array (taking O(n) time), and then performs another iteration to construct the result list using list comprehension (also taking O(n) time). The total time complexity is O(n) + O(n) = O(n).

The space complexity is O(n). The algorithm creates an auxiliary array f of size n to store the consecutive sequence lengths, which requires O(n) space. Additionally, the output list has size n - k + 1, which is also O(n) in the worst case. Therefore, the total space complexity is O(n).

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

Common Pitfalls

1. Misunderstanding the Consecutive Sequence Tracking

Pitfall: A common mistake is thinking that consecutive_length[i] needs to track the entire subarray's validity rather than just the length of consecutive increasing sequence ending at position i.

Wrong Approach:

# Incorrectly trying to check each subarray individually
for i in range(n - k + 1):
    is_valid = True
    for j in range(i, i + k - 1):
        if nums[j + 1] != nums[j] + 1:
            is_valid = False
            break
    result.append(nums[i + k - 1] if is_valid else -1)

Why it's wrong: This approach has O(n*k) time complexity and doesn't leverage the overlapping nature of subarrays.

Solution: Trust the preprocessing approach - if a sequence of length k ends at position i, then the subarray from i-k+1 to i is valid.

2. Off-by-One Errors in Index Calculation

Pitfall: Confusion about which indices represent the start vs. end of subarrays, leading to incorrect range calculations.

Wrong Approach:

# Incorrect index range for results
return [nums[i] if consecutive_length[i] >= k else -1 for i in range(k, n + 1)]  # Wrong!

Why it's wrong: The valid ending positions for subarrays of size k are from index k-1 to n-1, not k to n.

Solution: Remember that:

• First subarray: indices [0, k-1], ending at k-1
• Last subarray: indices [n-k, n-1], ending at n-1
• Total number of subarrays: n - k + 1

3. Incorrect Initialization of Consecutive Length Array

Pitfall: Initializing the consecutive length array to 0 instead of 1.

Wrong Approach:

consecutive_length = [0] * n  # Wrong initialization!

Why it's wrong: Every element forms at least a sequence of length 1 by itself. Starting with 0 would incorrectly handle single-element sequences and propagate errors.

Solution: Always initialize to 1, as each element is a valid sequence of length 1:

consecutive_length = [1] * n

4. Not Handling Edge Cases Properly

Pitfall: Failing to consider special cases like k=1 or when the array has only one element.

Example Issue:

# This might fail when k=1 because the loop doesn't execute
for i in range(1, n):
    if nums[i] == nums[i - 1] + 1:
        consecutive_length[i] = consecutive_length[i - 1] + 1
# When k=1, every single element should return itself as power

Solution: The current implementation actually handles k=1 correctly because:

• consecutive_length is initialized with all 1s
• When k=1, every position i where i >= 0 satisfies consecutive_length[i] >= 1
• The result correctly returns each element itself

5. Confusing Consecutive with Sorted

Pitfall: Checking only if elements are sorted in ascending order without verifying they differ by exactly 1.

Wrong Approach:

# Only checking if sorted, not if consecutive
if nums[i] > nums[i - 1]:  # Wrong! Should be nums[i] == nums[i - 1] + 1
    consecutive_length[i] = consecutive_length[i - 1] + 1

Why it's wrong: [2, 4, 6] is sorted but not consecutive. The problem requires elements to be both sorted AND consecutive (differ by exactly 1).

Solution: Always use the strict equality check:

if nums[i] == nums[i - 1] + 1:  # Correct - ensures exactly 1 difference