Find the Power of K-Size Subarrays I

MEDIUM

Description

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] <= 10⁵
1 <= k <= n

Approaches

Checkout 2 different approaches to solve Find the Power of K-Size Subarrays I. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find the Power of K-Size Subarrays I. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Find the Power of K-Size Subarrays I

Patterns:

Sliding Window

Data Structures:

Array