Finding the Power of K-Size Subarrays: A Comprehensive Guide

 Understanding the Problem

In this LeetCode problem, we're tasked with finding the "power" of all subarrays of size K within a given array of integers. The power of a subarray is defined as:

• Maximum element if all elements are consecutive and sorted in ascending order.
• -1 otherwise.

Brute Force Approach: A Simple Start

A straightforward approach involves iterating over every possible subarray of size K, checking its validity, and calculating its power.

Here's Java code for the same:

class Solution {
    public int[] resultsArray(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        for(int i = 0; i <= n-k; i++)
        {
            int f = 0;
            for(int j = i; j < i+k; j++)
            {
                // cur element = prev element + 1
                if(j > i && nums[j] != nums[j-1] + 1)
                {
                    f = 1;  // Violation of the rule was found
                    break;
                }
            }
            if(f == 0)
            {
                ans[i] = nums[i + k - 1];
            }
            else
            {
                ans[i] = -1;
            }
        }
        return ans;
    }
}

While this approach is intuitive, its time complexity is O(N * K), which can be inefficient for larger arrays and larger values of K.

Optimized Approach: Sliding Window Technique

A more efficient solution can be achieved using the sliding window technique. Here's how it works:

1. Initialize a window: Start with a window of size K.
2. Check the window's validity: Ensure the elements are consecutive and increasing.
3. Calculate the power: If valid, the maximum element is the power.
4. Slide the window: Move the window to the right by one element.
5. Repeat steps 2-4: Continue until the end of the array.

Here's Java code for the same:

class Solution {
    public int[] resultsArray(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        Arrays.fill(ans, -1);
        for(int beg = 0, end = 0; end < n; end++)
        {
            if(end > beg && nums[end] != nums[end - 1] + 1)
                beg = end;
            if(end - beg + 1 == k)
            {
                ans[beg] = nums[end];
                beg++;
            }
        }
        return ans;
    }
}

This approach has a time complexity of O(N), making it significantly faster than the brute force method.

Key Points to Remember

• Window Size: The window size remains constant throughout the process.
• Window Validity: We check if the elements within the window are consecutive and increasing.
• Power Calculation: If the window is valid, the last element (the maximum) is the power.
• Sliding the Window: We remove the first element and add a new element to maintain the window size.

By understanding these concepts and implementing the sliding window technique, we can efficiently solve the problem of finding the power of K-size subarrays.