Find the Power of K-Size Subarrays I

Problem Statement

In this problem, you are provided with an integer array nums of length n and a positive integer k. The task is to determine the power of all possible contiguous subarrays of nums with length k. The power of an array is uniquely defined based on the sequence and ordering of its elements:

• The power of an array is its maximum element if all its elements are consecutive numbers sorted in ascending order.
• If the elements are not consecutive or not sorted in ascending order, the power is -1.

The output should be an array results such that results[i] represents the power of the subarray starting from index i and ending at index i + k - 1. This problem challenges you to assess and deduce the sequence composition while keeping an eye on continuous subarray chunks of a given size.

Examples

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] → consecutive and ascending → power = 3
- [2, 3, 4] → consecutive and ascending → power = 4
- [3, 4, 3] → not consecutive → power = -1
- [4, 3, 2] → not sorted ascending → power = -1
- [3, 2, 5] → not consecutive → power = -1

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]

Explanation:

- [3,2] → not ascending → power = -1
- [2,3] → consecutive and ascending → power = 3
- [3,2] → not ascending → power = -1
- [2,3] → consecutive and ascending → power = 3
- [3,2] → not ascending → power = -1

Constraints

• 1 <= n == nums.length <= 500
• 1 <= nums[i] <= 10^5
• 1 <= k <= n

Approach and Intuition

Step-by-step process to solve the problem:

1. Initialize an empty list results to store the power of each subarray of size k.

2. Iterate through the main list nums and for each index i from 0 to n - k, perform:

   • Extract the subarray sub = nums[i : i + k].

   • Sort sub and check if each adjacent pair of elements has a difference of 1.

   • If the subarray is consecutive and sorted:

     • Append the maximum element of sub to results.

   • Otherwise:

     • Append -1 to results.

Intuition behind the solution:

• For a subarray to have a valid "power", its elements must be strictly consecutive and sorted in ascending order.
• Sorting and checking adjacent differences is a simple and reliable way to verify both conditions.
• Since n <= 500, this O(n * k log k) approach is acceptable, even with a nested loop and sorting inside each window.
• Special case: k = 1 — any single number is trivially consecutive and ascending, so its power is the number itself.

Solutions

class Solution {
public:
    vector<int> consecutiveArray(vector<int>& data, int target) {
        if (target == 1) {
            return data;  // Return original data if target is 1
        }
    
        size_t dataSize = data.size();
        vector<int> output(dataSize - target + 1, -1);  // Prepopulated output array
        int countConsecutive = 1;  // Track consecutive numbers
    
        for (size_t i = 0; i < dataSize - 1; ++i) {
            if (data[i] + 1 == data[i + 1]) {
                countConsecutive++;
            } else {
                countConsecutive = 1;  // Reset when the sequence breaks
            }
    
            // Store the last element of valid segment if the segment is long enough
            if (countConsecutive >= target) {
                output[i - target + 2] = data[i + 1];
            }
        }
    
        return output;
    }
};