Sponsored
Sponsored
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.
#include <vector>
bool isConsecutive(const std::vector<int>& nums, int start, int k) {
for (int i = 1; i < k; ++i) {
if (nums[start + i] != nums[start + i - 1] + 1) return false;
}
return true;
}
std::vector<int> findPowerOfSubarrays(const std::vector<int>& nums, int k) {
int n = nums.size();
std::vector<int> results(n - k + 1, -1);
for (int i = 0; i <= n - k; ++i) {
bool sortedAndConsecutive = true;
int maxElement = nums[i];
for (int j = 1; j < k; ++j) {
if (nums[i + j] < nums[i + j - 1] || nums[i + j] != nums[i + j - 1] + 1) {
sortedAndConsecutive = false;
break;
}
if (nums[i + j] > maxElement) maxElement = nums[i + j];
}
if (sortedAndConsecutive) results[i] = maxElement;
}
return results;
}
int main() {
std::vector<int> nums = {1, 2, 3, 4, 3, 2, 5};
int k = 3;
std::vector<int> results = findPowerOfSubarrays(nums, k);
for (int result : results) {
std::cout << result << " ";
}
return 0;
}Solve with full IDE support and test cases
In this C++ solution, the program iterates over each subarray of length k, checks the order and consecutiveness of elements, and stores the maximum if the subarray meets the criteria.
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.
1#include <stdio.h>
2#include <stdbool.h>
3
4bool isConsecutiveAndSorted(int *arr, int start, int k) {
5 for (int i = start + 1; i < start + k; i++) {
6 if (arr[i] != arr[i - 1] + 1) return false;
7 }
8 return true;
9}
10
11void findPowerWithSlidingWindow(int *nums, int n, int k, int *results) {
12 for (int i = 0; i <= n - k; i++) {
13 if (isConsecutiveAndSorted(nums, i, k)) {
14 int maxElem = nums[i + k - 1];
15 results[i] = maxElem;
16 } else {
17 results[i] = -1;
18 }
19 }
20}
21
22int main() {
23 int nums[] = {1, 2, 3, 4, 3, 2, 5};
24 int k = 3;
25 int n = sizeof(nums) / sizeof(nums[0]);
26 int results[n - k + 1];
27 findPowerWithSlidingWindow(nums, n, k, results);
28 for (int i = 0; i < n - k + 1; i++) {
29 printf("%d ", results[i]);
30 }
31 return 0;
32}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.