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 I

Number: 3522

Difficulty: Medium

Paid? No

Companies: Google, Bloomberg

Problem Description

Given an array of integers nums and a positive integer k, we need to compute the "power" of every contiguous subarray of size k. The power of a subarray is defined as the maximum element of the subarray if its elements are consecutive numbers sorted in ascending order; otherwise, the power is -1. Return an array where each element is the power of the corresponding subarray.

Key Insights

  • Use a sliding window of size k to traverse the array.
  • For each subarray, check if the elements are strictly increasing and consecutive.
  • To do this, iterate over the subarray and ensure that for every adjacent pair, the difference is exactly 1.
  • If the subarray meets the criteria, its power is the last (maximum) element; otherwise, the power is -1.

Space and Time Complexity

Time Complexity: O(n * k), where n is the number of elements in nums. For each of the (n - k + 1) windows, we perform k-1 comparisons. Space Complexity: O(n - k + 1) for the output array, and O(1) extra space is used within each window.

Solution

We use a simple sliding window approach to iterate through all contiguous subarrays of size k. For each window, we check if the subarray is sorted in ascending order with consecutive values. The check is performed by comparing adjacent elements to see if the difference is exactly 1. If the condition is satisfied, we record the last element (the maximum in the window) as the power of that subarray; otherwise, we record -1.

Code Solutions

# Python solution for the problem

def find_powers(nums, k):
    n = len(nums)
    results = []
    # Loop over every possible subarray of size k
    for i in range(n - k + 1):
        valid = True
        # Check if subarray nums[i:i+k] is consecutively sorted
        for j in range(i, i + k - 1):
            # If difference between consecutive numbers is not 1, mark as invalid
            if nums[j+1] - nums[j] != 1:
                valid = False
                break
        # Append maximum (the last element) if valid, otherwise -1
        results.append(nums[i+k-1] if valid else -1)
    return results

# Example usage:
print(find_powers([1,2,3,4,3,2,5], 3))
← Back to All Questions