Scale Engineer

Find the Power of K-Size Subarrays II

Med
#2889Time: O(n * k). The outer loop runs `n - k + 1` times, and for each iteration, the inner loop runs `k - 1` times. This leads to a quadratic time complexity in the worst case where `k` is proportional to `n`.Space: O(1) auxiliary space. The space required for the output array `results` is O(n-k+1), but auxiliary space is constant as we only use a few variables for loops and flags.
Patterns
Sliding Window
Data structures
Array

Prompt

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 <= 105
  • 1 <= nums[i] <= 106
  • 1 <= k <= n

Approaches

3 approaches with complexity analysis and trade-offs.

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 linear scan to check if it meets the specified conditions: being sorted in ascending order and having consecutive elements. This is the most straightforward but also the least efficient method.

Algorithm

  • Initialize an empty results array of size n - k + 1.
  • Loop with an index i from 0 to n - k. This i represents the starting index of a subarray.
  • For each i, assume the subarray is valid by setting a boolean flag, e.g., isValid = true.
  • Start a nested loop with index j from i + 1 to i + k - 1.
  • Inside the nested loop, check if nums[j] is equal to nums[j-1] + 1.
  • If the condition is ever false, the subarray is invalid. Set isValid = false and break the inner loop.
  • After the inner loop, if isValid is still true, the subarray's power is its last element, nums[i + k - 1]. Otherwise, its power is -1.
  • Store the calculated power in results[i].
  • After the outer loop finishes, return the results array.

Walkthrough

The brute-force method examines every single subarray of length k independently. For each subarray starting at index i, it iterates from the second element to the end of the subarray, verifying the condition nums[j] == nums[j-1] + 1. If this condition holds for all elements in the subarray, the power is the maximum element (which is the last element, nums[i+k-1]). If the condition fails at any point, the power is -1, and we can immediately move to the next subarray.

class Solution {    public long[] getPowerOfKSizeSubarrays(int[] nums, int k) {        int n = nums.length;        if (k == 0) {            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 + 1; j < i + k; j++) {                if (nums[j] != nums[j - 1] + 1) {                    isConsecutiveAndSorted = false;                    break;                }            }             if (isConsecutiveAndSorted) {                results[i] = nums[i + k - 1];            } else {                results[i] = -1;            }        }         return results;    }}

Complexity

Time

O(n * k). The outer loop runs `n - k + 1` times, and for each iteration, the inner loop runs `k - 1` times. This leads to a quadratic time complexity in the worst case where `k` is proportional to `n`.

Space

O(1) auxiliary space. The space required for the output array `results` is O(n-k+1), but auxiliary space is constant as we only use a few variables for loops and flags.

Trade-offs

Pros

  • Simple to understand and implement.

  • Correctly solves the problem without complex logic.

Cons

  • Highly inefficient for large n and k.

  • Very likely to result in a Time Limit Exceeded (TLE) error on competitive programming platforms for the given constraints.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem