Find the Power of K-Size Subarrays I

LeetCode 3254: Find the Power of K-Size Subarrays I Solution & Explanation

Problem Overview

TL;DR: Iterate through the array tracking the length of the current consecutive ascending sequence; if the sequence length is at least k at the end of a window, the result is the current element, otherwise -1.

In LeetCode 3254, "Find the Power of K-Size Subarrays I," we are given an integer array and a window size k. We must evaluate every contiguous subarray of size k. For a subarray to have a valid "power," its elements must be consecutive and sorted in ascending order (e.g., [3, 4, 5]). If valid, the power is the maximum element (which is simply the last element in a sorted sequence). If the elements are not consecutive or not sorted, the power is -1.

Brute Force Approach for Find the Power of K-Size Subarrays I

The naive approach involves extracting every subarray of size k and explicitly validating its elements.

1. Initialize a results array.
2. Iterate through nums from index i = 0 to n - k.
3. For each i, examine the window nums[i ... i + k - 1].
4. Iterate through this window to check if window[j+1] == window[j] + 1 for all adjacent pairs.
5. If the check passes, append the last element of the window to the results. Otherwise, append -1.

Pseudo-code:

1results = []
2for i in range(n - k + 1):
3    is_valid = True
4    for j in range(i, i + k - 1):
5        if nums[j + 1] != nums[j] + 1:
6            is_valid = False
7            break
8    if is_valid:
9        results.append(nums[i + k - 1])
10    else:
11        results.append(-1)

Complexity Analysis: The time complexity is $O(n \cdot k)$ because for each of the $O(n)$ windows, we perform $O(k)$ comparisons. While the constraints for "Find the Power of K-Size Subarrays I" ($n \le 500$) allow this to pass, this approach is computationally inefficient and will fail Time Limit constraints on larger datasets (like in the version II of this problem).

Algorithm Strategy: Sliding Window Patterns

1. Initialization: Create a result array initialized to -1. Initialize a counter consecutive_cnt to 1.
2. Iterate: Traverse the array from index 0 to n-1.
3. State Update:
   • Compare nums[i] with nums[i-1].
   • If nums[i] == nums[i-1] + 1, increment consecutive_cnt.
   • Otherwise, reset consecutive_cnt to 1.
4. Window Validation:
   • Check if the current index i represents the end of a valid window size (i.e., i >= k - 1).
   • If consecutive_cnt >= k, update the corresponding entry in the result array to nums[i].
   • Note: Since the result array was initialized to -1, we do not need to explicitly set -1 for invalid windows.

Execution Flow

Let nums = [1, 2, 3, 4, 3, 2, 5] and k = 3. Result array size is $7 - 3 + 1 = 5$. Initialize res = [-1, -1, -1, -1, -1].

1. i = 0: nums[0] = 1. consecutive_cnt = 1. Window not full ($0 < 2$).
2. i = 1: nums[1] = 2. $2 == 1 + 1$. consecutive_cnt becomes 2. Window not full.
3. i = 2: nums[2] = 3. $3 == 2 + 1$. consecutive_cnt becomes 3.
   • Window full ($2 \ge 2$).
   • consecutive_cnt (3) $\ge k$ (3).
   • res[0] = nums[2] = 3.
4. i = 3: nums[3] = 4. $4 == 3 + 1$. consecutive_cnt becomes 4.
   • Window full.
   • consecutive_cnt (4) $\ge k$ (3).
   • res[1] = nums[3] = 4.
5. i = 4: nums[4] = 3. $3 \neq 4 + 1$. consecutive_cnt resets to 1.
   • Window full.
   • consecutive_cnt (1) $< k$ (3). Result remains -1.
6. i = 5: nums[5] = 2. $2 \neq 3 + 1$. consecutive_cnt resets to 1.
   • Window full.
   • consecutive_cnt (1) $< k$ (3). Result remains -1.
7. i = 6: nums[6] = 5. $5 \neq 2 + 1$. consecutive_cnt resets to 1.
   • Window full.
   • consecutive_cnt (1) $< k$ (3). Result remains -1.

Final Output: [3, 4, -1, -1, -1].

Proof of Correctness

The algorithm relies on the property that a subarray nums[j...i] is strictly consecutive and sorted if and only if every adjacent pair within that range satisfies the condition $x_{m+1} = x_m + 1$. The variable consecutive_cnt maintains the size of the largest suffix of nums[0...i] that satisfies this property. If consecutive_cnt >= k at index i, it guarantees that the subarray nums[i-k+1...i] is valid. Since the problem defines "power" as the maximum element of a sorted array, and the array is sorted ascending, the last element nums[i] is strictly the maximum.

Pattern Reuse Notes

The Sliding Window - Fixed Size pattern used here is applicable to several other popular interview questions:

• LeetCode 346: Moving Average from Data Stream (Maintains a sum over a fixed window)
• LeetCode 643: Maximum Average Subarray I (Optimizes sum calculation using sliding window)
• LeetCode 2985: Calculate Compressed Mean (Similar statistical calculation over streams)
• LeetCode 3318: Find X-Sum of All K-Long Subarrays I (Complex aggregation over fixed windows)

In all these problems, the key is to update the window state incrementally (add new element, remove old element) rather than recalculating from scratch.

Reference Implementation

C++ Solution for LeetCode 3254

1#include <vector>
2#include <numeric>
3
4class Solution {
5public:
6    std::vector<int> resultsArray(std::vector<int>& nums, int k) {
7        int n = nums.size();
8        if (n == 0) return {};
9        
10        std::vector<int> results(n - k + 1, -1);
11        int consecutive_cnt = 0;
12        
13        for (int i = 0; i < n; ++i) {
14            // Check if current element continues the sequence
15            if (i > 0 && nums[i] == nums[i - 1] + 1) {
16                consecutive_cnt++;
17            } else {
18                consecutive_cnt = 1;
19            }
20            
21            // If we have processed at least k elements
22            if (i >= k - 1) {
23                if (consecutive_cnt >= k) {
24                    results[i - k + 1] = nums[i];
25                }
26            }
27        }
28        
29        return results;
30    }
31};

Java Solution for LeetCode 3254

1class Solution {
2    public int[] resultsArray(int[] nums, int k) {
3        int n = nums.length;
4        int[] results = new int[n - k + 1];
5        // Initialize results with -1
6        for (int i = 0; i < results.length; i++) {
7            results[i] = -1;
8        }
9        
10        int consecutiveCnt = 0;
11        
12        for (int i = 0; i < n; i++) {
13            if (i > 0 && nums[i] == nums[i - 1] + 1) {
14                consecutiveCnt++;
15            } else {
16                consecutiveCnt = 1;
17            }
18            
19            // Check if the window is valid
20            if (i >= k - 1) {
21                if (consecutiveCnt >= k) {
22                    results[i - k + 1] = nums[i];
23                }
24            }
25        }
26        
27        return results;
28    }
29}

Python Solution for LeetCode 3254

1from typing import List
2
3class Solution:
4    def resultsArray(self, nums: List[int], k: int) -> List[int]:
5        n = len(nums)
6        results = [-1] * (n - k + 1)
7        consecutive_cnt = 0
8        
9        for i in range(n):
10            # Check continuity with previous element
11            if i > 0 and nums[i] == nums[i - 1] + 1:
12                consecutive_cnt += 1
13            else:
14                consecutive_cnt = 1
15            
16            # If the current window size is reached
17            if i >= k - 1:
18                if consecutive_cnt >= k:
19                    results[i - k + 1] = nums[i]
20                    
21        return results