You are given an array of integers nums of length n and a positive integer k.
The power of an array is defined as:
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 <= 5001 <= nums[i] <= 1051 <= k <= nWe can solve this problem by checking all possible subarrays of size k explicitly. For each subarray, we check if it is sorted and if the elements are consecutive. If both conditions are met, we calculate the power as the maximum element of the subarray. Otherwise, the power is -1.
This C implementation uses a function to check whether each subarray of size k is sorted and the elements are consecutive. If both conditions are satisfied, the function calculates the power as the maximum element of the subarray.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * k) because we process each element of each subarray of size k.
Space Complexity: O(n-k+1) for storing the results array.
This approach employs a sliding window technique to process each subarray of size k efficiently. We slide over the array and check whether each segment meets the criteria of being both sorted and consecutive. This reduces unnecessary re-checks by leveraging overlapping subarray properties.
This C implementation uses a function to verify both order and consecutiveness of elements in a k-length sliding window. The maximum element is calculated if the conditions are met.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * k), reduced by potentially not rechecking unchanged segments.
Space Complexity: O(n-k+1) for the results array.
| Approach | Complexity |
|---|---|
| Brute Force Checking of Subarrays | Time Complexity: |
| Optimized Sliding Window Technique | Time Complexity: |
Find the Power of K-Size Subarrays I - Leetcode 3254 - Python • NeetCodeIO • 8,065 views views
Watch 9 more video solutions →Practice Find the Power of K-Size Subarrays I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor