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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Power of K-Size Subarrays II

Number: 3523

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an array of integers nums and a positive integer k, you need to find the "power" for every contiguous subarray of size k. A subarray’s power is defined as its maximum element if all elements in the subarray are consecutive and sorted in ascending order; otherwise, the power is -1. Return an array where each element corresponds to the power of the respective subarray.

Key Insights

  • The condition "consecutive and sorted" implies that for any valid subarray, each adjacent element difference must be exactly 1.
  • For a subarray of length k, check that every adjacent pair satisfies (nums[i+1] - nums[i] == 1). This is equivalent to ensuring that the sum of these "differences-satisfied" flags is k - 1.
  • Use a sliding window (or prefix sum array on a differences array) to efficiently compute this for each subarray.
  • When the subarray meets the criteria, the maximum value (because the array is sorted ascending) is the last element of the subarray.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the array, since we make a single pass to compute the differences and another pass to evaluate each window. Space Complexity: O(n), primarily for the differences array (or prefix sum array).

Solution

We first precompute a differences array where each element is 1 if the difference between consecutive elements in nums is exactly 1, and 0 otherwise. For k = 1, every single element is trivially valid. Then, we construct a prefix sum array of the differences. For each subarray starting at index i, the sum of differences over that window (which spans indices from i to i+k-2) should equal k - 1 if it is a valid subarray. If valid, the power is the last element in the subarray; otherwise, the power is -1. This approach ensures that each subarray is checked in constant time after the preprocessing step.

Code Solutions

# Python solution with line-by-line comments

def findPowerOfSubarrays(nums, k):
    n = len(nums)
    # When subarray size is 1, each element trivially qualifies.
    if k == 1:
        return nums[:]  # each element is its own power

    # Build the differences array: diff[i] = 1 if nums[i+1] - nums[i] == 1, else 0
    diff = [1 if nums[i+1] - nums[i] == 1 else 0 for i in range(n - 1)]

    # Build prefix sum array for the diff list.
    prefix = [0] * (len(diff) + 1)
    for i in range(len(diff)):
        prefix[i+1] = prefix[i] + diff[i]

    results = []
    # For every subarray of length k, check if the total sum of diffs equals k-1.
    for i in range(n - k + 1):
        # Range in diff array corresponds to [i, i+k-2]
        # Using prefix sums, the sum is prefix[i+k-1] - prefix[i]
        if prefix[i+k-1] - prefix[i] == k - 1:
            # Valid subarray, power is the last element
            results.append(nums[i+k-1])
        else:
            results.append(-1)
    return results

# Example usage
if __name__ == "__main__":
    print(findPowerOfSubarrays([1,2,3,4,3,2,5], 3))
    print(findPowerOfSubarrays([2,2,2,2,2], 4))
    print(findPowerOfSubarrays([3,2,3,2,3,2], 2))
← Back to All Questions