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

Problem Overview: You are given an integer array and a window size k. For every contiguous subarray of length k, determine whether the elements form a strictly increasing consecutive sequence where nums[i] + 1 = nums[i+1]. If the condition holds, the subarray's power is the maximum element (the last element of that window). Otherwise, the power is -1. The result is an array containing the power of each k-length window.

Approach 1: Brute Force Checking of Subarrays (Time: O(n*k), Space: O(1))

The straightforward solution checks every subarray of size k. For each starting index, iterate through the next k-1 elements and verify the consecutive condition nums[j] + 1 == nums[j+1]. If any pair breaks the rule, the current window is invalid and its power becomes -1. If all comparisons succeed, return the last element of that window as the power. This method directly follows the problem definition and is useful for validating logic during implementation. However, because each window requires up to k comparisons, the total runtime grows to O(n*k) for an array of size n. The approach uses constant extra space since it only tracks indices and comparisons.

Approach 2: Optimized Sliding Window Technique (Time: O(n), Space: O(1))

The optimized solution observes that consecutive windows overlap heavily. Instead of rechecking all k elements each time, track the length of the current streak where adjacent numbers increase by exactly one. Iterate through the array once and update a counter whenever nums[i] == nums[i-1] + 1. If the condition breaks, reset the streak length. For a window ending at index i, the subarray of size k is valid if the streak length is at least k. When valid, record nums[i] as the power; otherwise record -1. This effectively converts repeated window validation into a single pass over the array. The algorithm runs in linear time O(n) with constant space.

This pattern is common in problems involving contiguous segments and overlapping windows. Understanding how to reuse information from the previous window is the key optimization in sliding window techniques. Since the data is processed sequentially, the solution relies only on simple comparisons and counters over the array.

Recommended for interviews: Start by describing the brute force approach to show you understand the requirement for validating each window. Then transition to the sliding window optimization that tracks consecutive increments in a single pass. Interviewers typically expect the O(n) sliding window solution because it demonstrates pattern recognition and efficient handling of overlapping subarrays.