# Find the Power of K-Size Subarrays II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-power-of-k-size-subarrays-ii)
Canonical: https://scaleengineer.com/dsa/problems/find-the-power-of-k-size-subarrays-ii
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array
---
## Problem
You are given an array of integers `nums` of length `n` and a _positive_ integer `k`.

The **power** of an array is defined as:

* Its **maximum** element if _all_ of its elements are **consecutive** and **sorted** in **ascending** order.
* \-1 otherwise.

You need to find the **power** of all subarrays of `nums` of size `k`.

Return an integer array `results` of size `n - k + 1`, where `results[i]` is the _power_ of `nums[i..(i + k - 1)]`.

**Example 1:**

**Input:** nums = \[1,2,3,4,3,2,5\], k = 3

**Output:** \[3,4,-1,-1,-1\]

**Explanation:**

There are 5 subarrays of `nums` of size 3:

* `[1, 2, 3]` with the maximum element 3.
* `[2, 3, 4]` with the maximum element 4.
* `[3, 4, 3]` whose elements are **not** consecutive.
* `[4, 3, 2]` whose elements are **not** sorted.
* `[3, 2, 5]` whose elements are **not** consecutive.

**Example 2:**

**Input:** nums = \[2,2,2,2,2\], k = 4

**Output:** \[-1,-1\]

**Example 3:**

**Input:** nums = \[3,2,3,2,3,2\], k = 2

**Output:** \[-1,3,-1,3,-1\]

**Constraints:**

* `1 <= n == nums.length <= 105`
* `1 <= nums[i] <= 106`
* `1 <= k <= n`

# Approaches
## Brute Force Iteration
This approach directly translates the problem statement into code. It iterates through each possible subarray of size `k`, and for each one, it performs a linear scan to check if it meets the specified conditions: being sorted in ascending order and having consecutive elements. This is the most straightforward but also the least efficient method.
**Time:** O(n * k). The outer loop runs `n - k + 1` times, and for each iteration, the inner loop runs `k - 1` times. This leads to a quadratic time complexity in the worst case where `k` is proportional to `n`. · **Space:** O(1) auxiliary space. The space required for the output array `results` is O(n-k+1), but auxiliary space is constant as we only use a few variables for loops and flags.
**Pros:** Simple to understand and implement.; Correctly solves the problem without complex logic.
**Cons:** Highly inefficient for large `n` and `k`.; Very likely to result in a Time Limit Exceeded (TLE) error on competitive programming platforms for the given constraints.
### Explanation
The brute-force method examines every single subarray of length `k` independently. For each subarray starting at index `i`, it iterates from the second element to the end of the subarray, verifying the condition `nums[j] == nums[j-1] + 1`. If this condition holds for all elements in the subarray, the power is the maximum element (which is the last element, `nums[i+k-1]`). If the condition fails at any point, the power is -1, and we can immediately move to the next subarray.

```java
class Solution {
    public long[] getPowerOfKSizeSubarrays(int[] nums, int k) {
        int n = nums.length;
        if (k == 0) {
            return new long[0];
        }
        long[] results = new long[n - k + 1];

        for (int i = 0; i <= n - k; i++) {
            boolean isConsecutiveAndSorted = true;
            // Check the subarray nums[i...i+k-1]
            for (int j = i + 1; j < i + k; j++) {
                if (nums[j] != nums[j - 1] + 1) {
                    isConsecutiveAndSorted = false;
                    break;
                }
            }

            if (isConsecutiveAndSorted) {
                results[i] = nums[i + k - 1];
            } else {
                results[i] = -1;
            }
        }

        return results;
    }
}
```
### Algorithm
- Initialize an empty `results` array of size `n - k + 1`.
- Loop with an index `i` from `0` to `n - k`. This `i` represents the starting index of a subarray.
- For each `i`, assume the subarray is valid by setting a boolean flag, e.g., `isValid = true`.
- Start a nested loop with index `j` from `i + 1` to `i + k - 1`.
- Inside the nested loop, check if `nums[j]` is equal to `nums[j-1] + 1`.
- If the condition is ever false, the subarray is invalid. Set `isValid = false` and break the inner loop.
- After the inner loop, if `isValid` is still true, the subarray's power is its last element, `nums[i + k - 1]`. Otherwise, its power is `-1`.
- Store the calculated power in `results[i]`.
- After the outer loop finishes, return the `results` array.

## Pre-computation with Dynamic Programming
This method improves upon the brute-force approach by pre-calculating information to avoid redundant checks. It uses a dynamic programming technique to compute the length of consecutive runs of numbers in a single pass. A subarray `nums[i...i+k-1]` is valid if and only if the run of consecutive numbers ending at index `i+k-1` is at least `k` long. This pre-computation allows us to determine the power of each subarray in constant time.
**Time:** O(n). We perform two separate linear passes over the data: one to compute `runLength` and another to compute `results`. Both take `O(n)` time. · **Space:** O(n). We need an auxiliary array `runLength` of size `n` to store the pre-computed run lengths.
**Pros:** Much faster than the brute-force approach with a linear time complexity.; The logic is still relatively straightforward to follow.
**Cons:** Requires extra space proportional to the input size, which might be a concern for very large inputs under strict memory constraints.
### Explanation
The core idea is to transform the problem. A subarray `nums[i...i+k-1]` is consecutive and sorted if and only if `nums[j] == nums[j-1] + 1` for all `j` from `i+1` to `i+k-1`. We can create an auxiliary array, `runLength`, where `runLength[j]` stores the length of the valid consecutive sequence ending at that index `j`. This array can be built in `O(n)` time. Once we have this `runLength` array, we can find the power for each k-size subarray in `O(1)` time. For a subarray ending at index `endIdx`, we just need to check if `runLength[endIdx]` is at least `k`.

```java
class Solution {
    public long[] getPowerOfKSizeSubarrays(int[] nums, int k) {
        int n = nums.length;
        if (k == 0) {
            return new long[0];
        }
        if (k == 1) {
            long[] results = new long[n];
            for (int i = 0; i < n; i++) {
                results[i] = nums[i];
            }
            return results;
        }

        // runLength[i] stores the length of the consecutive run ending at index i
        int[] runLength = new int[n];
        runLength[0] = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] == nums[i - 1] + 1) {
                runLength[i] = runLength[i - 1] + 1;
            } else {
                runLength[i] = 1;
            }
        }

        long[] results = new long[n - k + 1];
        for (int i = 0; i <= n - k; i++) {
            int windowEndIndex = i + k - 1;
            // Check if the run of consecutive numbers ending at windowEndIndex
            // is long enough to cover the entire window.
            if (runLength[windowEndIndex] >= k) {
                results[i] = nums[windowEndIndex];
            } else {
                results[i] = -1;
            }
        }

        return results;
    }
}
```
### Algorithm
- Create an integer array, `runLength`, of the same size as `nums`. `runLength[j]` will store the length of the consecutive, sorted sequence ending at index `j`.
- Initialize `runLength[0] = 1`.
- Iterate from `j = 1` to `n - 1`. If `nums[j] == nums[j-1] + 1`, set `runLength[j] = runLength[j-1] + 1`. Otherwise, a new run starts, so set `runLength[j] = 1`.
- Initialize the `results` array of size `n - k + 1`.
- Iterate from `i = 0` to `n - k`. This `i` is the start of the window.
- The window ends at index `endIdx = i + k - 1`.
- Check if `runLength[endIdx] >= k`. If it is, the entire window is part of a valid run. The power is `nums[endIdx]`.
- If `runLength[endIdx] < k`, the window is not a valid run. The power is `-1`.
- Store the result in `results[i]`.
- Return the `results` array.

## Optimized Sliding Window
This is the most efficient approach in terms of both time and space. It uses a sliding window of size `k` and maintains a count of adjacent pairs that satisfy the consecutive condition (`nums[j] == nums[j-1] + 1`). A subarray is valid if and only if it contains `k-1` such pairs. As the window slides, this count is updated in constant time by subtracting the contribution of the element that leaves the window and adding the contribution of the element that enters. This avoids redundant calculations entirely.
**Time:** O(n). The initial window setup takes `O(k)`. The subsequent `n-k` slides each take `O(1)` time for updates. The total time is `O(k + (n-k)) = O(n)`. · **Space:** O(1) auxiliary space. We only use a few variables to keep track of the count and loop indices, regardless of the input size.
**Pros:** Optimal time complexity of O(n).; Optimal auxiliary space complexity of O(1).; Highly efficient for large inputs.
**Cons:** The logic for updating the counter at the window boundaries can be slightly more complex to implement correctly compared to other approaches.
### Explanation
We start by analyzing the first window of size `k` and counting how many adjacent pairs are consecutive. A window is valid if this count is exactly `k-1`. Then, as we slide the window one position to the right, we don't need to re-scan the whole window. We only need to consider two pairs: the one leaving the window from the left and the one entering from the right. We adjust our count based on these two pairs. This `O(1)` update per slide allows us to process the entire array in linear time with constant extra space.

```java
class Solution {
    public long[] getPowerOfKSizeSubarrays(int[] nums, int k) {
        int n = nums.length;
        if (k == 0) {
            return new long[0];
        }
        long[] results = new long[n - k + 1];

        if (k == 1) {
            for (int i = 0; i < n; i++) {
                results[i] = nums[i];
            }
            return results;
        }

        // Initialize for the first window
        int consecutivePairs = 0;
        for (int i = 1; i < k; i++) {
            if (nums[i] == nums[i - 1] + 1) {
                consecutivePairs++;
            }
        }

        if (consecutivePairs == k - 1) {
            results[0] = nums[k - 1];
        } else {
            results[0] = -1;
        }

        // Slide the window
        for (int i = 1; i <= n - k; i++) {
            // Element leaving the window is nums[i-1].
            // The pair (nums[i-1], nums[i]) is no longer part of the window's checks.
            if (nums[i] == nums[i - 1] + 1) {
                consecutivePairs--;
            }

            // Element entering the window is nums[i+k-1].
            // The new pair to check is (nums[i+k-2], nums[i+k-1]).
            if (nums[i + k - 1] == nums[i + k - 2] + 1) {
                consecutivePairs++;
            }

            if (consecutivePairs == k - 1) {
                results[i] = nums[i + k - 1];
            } else {
                results[i] = -1;
            }
        }

        return results;
    }
}
```
### Algorithm
- Initialize a `results` array of size `n - k + 1`.
- Initialize a counter, `consecutivePairs`, to 0.
- **First Window:** Iterate from `j = 1` to `k - 1` to populate the counter for the initial window `nums[0...k-1]`. If `nums[j] == nums[j-1] + 1`, increment `consecutivePairs`.
- After the initial setup, check if `consecutivePairs == k - 1`. If so, the first subarray is valid, and `results[0]` is `nums[k-1]`. Otherwise, `results[0]` is `-1`.
- **Slide the Window:** Loop from `i = 1` to `n - k`. In each iteration, the window slides one position to the right.
- **Update for leaving element:** The pair `(nums[i-1], nums[i])` is leaving the window's scope. If this pair was consecutive (`nums[i] == nums[i-1] + 1`), decrement `consecutivePairs`.
- **Update for entering element:** The pair `(nums[i+k-2], nums[i+k-1])` is entering the window's scope. If this new pair is consecutive, increment `consecutivePairs`.
- After updating the counter, check if `consecutivePairs == k - 1`. If it is, the current window `nums[i...i+k-1]` is valid. Set `results[i] = nums[i+k-1]`. Otherwise, set `results[i] = -1`.
- Return the `results` array.

# Solutions
### Java

```java
class Solution {
public
  int[] resultsArray(int[] nums, int k) {
    int n = nums.length;
    int[] f = new int[n];
    Arrays.fill(f, 1);
    for (int i = 1; i < n; ++i) {
      if (nums[i] == nums[i - 1] + 1) {
        f[i] = f[i - 1] + 1;
      }
    }
    int[] ans = new int[n - k + 1];
    for (int i = k - 1; i < n; ++i) {
      ans[i - k + 1] = f[i] >= k ? nums[i] : -1;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> resultsArray(vector<int> &nums, int k) {
    int n = nums.size();
    int f[n];
    f[0] = 1;
    for (int i = 1; i < n; ++i) {
      f[i] = nums[i] == nums[i - 1] + 1 ? f[i - 1] + 1 : 1;
    }
    vector<int> ans;
    for (int i = k - 1; i < n; ++i) {
      ans.push_back(f[i] >= k ? nums[i] : -1);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def resultsArray(self, nums: List[int], k: int) -> List[int]: n = len(nums) f = [1] * n for i in range(1, n): if nums[i] == nums[i - 1] + 1: f[i] = f[i - 1] + 1 return [nums[i] if f[i] >= k else - 1 for i in range(k - 1, n)]

```