We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Power of K-Size Subarrays II

Difficulty: Medium

Problem 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; otherwise, it is -1. You need to find the power of all subarrays of nums of size k and return an integer array results where results[i] is the power of nums[i..(i + k - 1)].

Key Insights

  • A subarray must have consecutive integers to have a valid power.
  • The maximum element of the subarray is only valid if the elements are sorted and consecutive.
  • Efficiently checking for consecutive integers can be done using a sliding window approach.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution employs a sliding window technique to efficiently iterate through the array. For each subarray of size k, we check if the elements are consecutive and sorted. This can be done by checking the minimum and maximum of the subarray and ensuring that the range of numbers matches the length of the subarray. A set can also be used to ensure all numbers are unique.

Code Solutions

def findPowerOfKSizeSubarrays(nums, k):
    n = len(nums)
    results = []
    
    for i in range(n - k + 1):
        subarray = nums[i:i + k]
        min_val = min(subarray)
        max_val = max(subarray)
        
        # Check for consecutive integers
        if max_val - min_val == k - 1 and len(set(subarray)) == k:
            results.append(max_val)
        else:
            results.append(-1)
    
    return results
← Back to All Questions