We 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.
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.
1def find_power_of_subarrays(nums, k):
2 n = len(nums)
3 results = [-1] * (n - k + 1)
4 for i in range(n - k + 1):
5 sorted_and_consecutive = True
6 max_element = nums[i]
7 for j in range(1, k):
8 if nums[i + j] < nums[i + j - 1] or nums[i + j] != nums[i + j - 1] + 1:
9 sorted_and_consecutive = False
10 break
11 if nums[i + j] > max_element:
12 max_element = nums[i + j]
13 if sorted_and_consecutive:
14 results[i] = max_element
15 return results
16
17nums = [1, 2, 3, 4, 3, 2, 5]
18k = 3
19print(find_power_of_subarrays(nums, k))In this Python solution, each subarray of length k is examined to ascertain the order and consecutiveness of elements, determining the power when conditions are met.
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.
Time Complexity: O(n * k), reduced by potentially not rechecking unchanged segments.
Space Complexity: O(n-k+1) for the results array.
1function findPowerWithSlidingWindow(nums, k) {
2 const n = nums.length;
3 const results = new Array(n - k + 1).fill(-1);
4 for (let i = 0; i <= n - k; i++) {
5 let sortedAndConsecutive = true;
6 for (let j = 1; j < k; j++) {
7 if (nums[i + j] != nums[i + j - 1] + 1) {
8 sortedAndConsecutive = false;
9 break;
10 }
11 }
12 results[i] = sortedAndConsecutive ? nums[i + k - 1] : -1;
13 }
14 return results;
15}
16
17const nums = [1, 2, 3, 4, 3, 2, 5];
18const k = 3;
19console.log(findPowerWithSlidingWindow(nums, k));A JavaScript technique using sliding window to ensure each subarray is efficiently checked for order and consecutiveness.