# Find the Power of K-Size Subarrays I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-power-of-k-size-subarrays-i)
Canonical: https://scaleengineer.com/dsa/problems/find-the-power-of-k-size-subarrays-i
**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 <= 500`
* `1 <= nums[i] <= 105`
* `1 <= k <= n`

# Approaches
## Brute-Force Iteration over Subarrays
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 separate check to see if it meets the criteria for a positive power. A subarray is valid if its elements are both sorted in ascending order and consecutive. This is equivalent to checking if `subarray[j+1] == subarray[j] + 1` for all `j`.
**Time:** O(n * k). The outer loop runs `n - k + 1` times, and for each iteration, the inner loop runs `k - 1` times. This results in a total of approximately `(n - k + 1) * (k - 1)` operations. · **Space:** O(n) or O(n - k + 1) for the result array. If the output array is not considered, the space complexity is O(1) as we only use a few variables.
**Pros:** Simple to understand and implement.; It is a direct and straightforward implementation of the problem's requirements.
**Cons:** Inefficient for large `n` and `k` due to its quadratic time complexity in the worst case.; Performs redundant comparisons for overlapping portions of consecutive subarrays.
### Explanation
We initialize an array `results` of size `n - k + 1` to store the power of each subarray. The main logic involves a nested loop structure. The outer loop iterates from `i = 0` to `n - k`, where `i` represents the starting index of each k-sized subarray. For each subarray starting at `i`, we use an inner loop to verify if it's consecutive and sorted. This inner loop runs from `j = i` to `i + k - 2` and checks the condition `nums[j+1] == nums[j] + 1`. A boolean flag, `isValid`, tracks the validity of the current subarray. If the condition ever fails, the flag is set to `false`, and we can stop checking the current subarray. If the inner loop completes and the flag remains `true`, the subarray's power is its last (and maximum) element, `nums[i+k-1]`. Otherwise, the power is `-1`. This value is then stored in the `results` array at index `i`.

```java
class Solution {
    public long[] findPowerOfKSizeSubarrays(int[] nums, int k) {
        int n = nums.length;
        if (k > n) {
            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; j < i + k - 1; j++) {
                if (nums[j+1] != nums[j] + 1) {
                    isConsecutiveAndSorted = false;
                    break;
                }
            }
            
            if (isConsecutiveAndSorted) {
                results[i] = nums[i + k - 1];
            } else {
                results[i] = -1;
            }
        }
        
        return results;
    }
}
```
### Algorithm
- Create a result array `results` of size `n - k + 1`.
- Loop `i` from `0` to `n - k` to iterate through all possible starting positions of a subarray.
- For each `i`, assume the subarray `nums[i...i+k-1]` is valid by setting a flag `isValid = true`.
- Start an inner loop `j` from `i` to `i + k - 2` to check adjacent elements.
- Inside the inner loop, if `nums[j+1]` is not equal to `nums[j] + 1`, the subarray is not consecutive and sorted. Set `isValid = false` and break the inner loop.
- After the inner loop finishes, if `isValid` is still `true`, it means all elements were consecutive and sorted. The power is the maximum element, which is `nums[i + k - 1]`. Store this in `results[i]`.
- If `isValid` is `false`, the power is `-1`. Store `-1` in `results[i]`.
- After iterating through all possible starting positions, return the `results` array.

## Optimized Single Pass Approach
This approach improves upon the brute-force method by avoiding redundant computations. It makes a single pass through the array while keeping track of the length of the current run of consecutive, increasing numbers. By knowing the length of the run ending at any given index, we can determine if a k-sized subarray ending at that index is valid in constant time, leading to an overall linear time complexity.
**Time:** O(n). We iterate through the `nums` array only once, and each step inside the loop takes constant time. · **Space:** O(n) or O(n - k + 1) for the result array. The extra space used for variables like `consecutiveRunLength` is O(1).
**Pros:** Highly efficient with a linear time complexity, making it suitable for larger inputs.; Avoids redundant calculations by cleverly reusing information about consecutive runs from the previous element.
**Cons:** The logic can be slightly less intuitive to devise compared to the brute-force approach.
### Explanation
The core idea is to efficiently determine if a subarray is valid without re-scanning it every time. We can do this by maintaining a count of how many consecutive elements form an increasing sequence. We iterate through the `nums` array once, from left to right. We use a variable, `consecutiveRunLength`, to store the length of the current sequence of numbers where each element is one greater than the previous one.

As we iterate to index `i`, we compare `nums[i]` with `nums[i-1]`. If `nums[i] == nums[i-1] + 1`, we increment `consecutiveRunLength`. If not, the sequence is broken, and we reset `consecutiveRunLength` to 1 (for the new run starting at `nums[i]`).

When our iteration index `i` reaches `k-1`, we have our first full subarray of size `k` (from index 0 to `k-1`). We check if our `consecutiveRunLength` is at least `k`. If it is, the subarray is valid, and its power is `nums[i]`. Otherwise, it's -1. We continue this process for all subsequent elements. For any index `i >= k-1`, we check the subarray ending at `i`. If `consecutiveRunLength >= k`, the power of `results[i-k+1]` is `nums[i]`; otherwise, it's -1. This single pass is highly efficient.

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

        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] == nums[i-1] + 1) {
                consecutiveRunLength++;
            } else {
                consecutiveRunLength = 1;
            }

            if (i >= k - 1) {
                int resultIndex = i - k + 1;
                if (consecutiveRunLength >= k) {
                    results[resultIndex] = nums[i];
                } else {
                    results[resultIndex] = -1;
                }
            }
        }
        return results;
    }
}
```
### Algorithm
- Initialize a result array `results` of size `n - k + 1`.
- Initialize a counter `consecutiveRunLength = 0` to track the length of the current run of consecutive increasing numbers.
- Iterate through the `nums` array with an index `i` from `0` to `n - 1`.
- In each iteration, check if `i > 0` and `nums[i] == nums[i-1] + 1`. 
- If true, the run continues, so increment `consecutiveRunLength`.
- If false, the run is broken. Reset `consecutiveRunLength` to `1` (since `nums[i]` itself forms a run of length 1).
- Once the loop index `i` is `k - 1` or greater, we have a full k-sized window ending at `i`.
- The corresponding index in the `results` array is `resultIndex = i - k + 1`.
- Check if `consecutiveRunLength` is at least `k`. If it is, the subarray `nums[i-k+1...i]` is valid. Its power is the maximum element, `nums[i]`. Set `results[resultIndex] = nums[i]`.
- Otherwise, the subarray is not valid. Set `results[resultIndex] = -1`.
- After the loop completes, return `results`.

# 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)]

```