Find the Power of K-Size Subarrays I - Problem

You are given an array of integers nums of length n and a positive integer k.

The power of an array is defined as:

Its maximum element if all of its elements are consecutive and sorted in ascending order.
-1 otherwise.

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)].

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,3,4], k = 3

› Output: [3,4]

💡 Note: First subarray [1,2,3] is consecutive ascending, power = 3. Second subarray [2,3,4] is consecutive ascending, power = 4.

Example 2 — Non-consecutive Elements

$ Input: nums = [2,2,2,2,2], k = 4

› Output: [-1,-1]

💡 Note: All elements are the same (not ascending), so no subarray has power. Both [2,2,2,2] subarrays return -1.

Example 3 — Gap in Sequence

$ Input: nums = [3,2,3,2,3], k = 2

› Output: [-1,-1,-1,-1]

💡 Note: No 2-element subarray has consecutive ascending elements: [3,2], [2,3], [3,2], [2,3] all have gaps or are not ascending.

Constraints

1 ≤ n ≤ 500
1 ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ n

Visualization

Tap to expand

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that we need to check if k consecutive elements form an ascending sequence. The brute force approach checks each subarray individually in O(n×k) time. The sliding window approach optimizes this to O(n) by tracking consecutive count as we slide. Best approach is sliding window with Time: O(n), Space: O(1).

Common Approaches

✓ Dp 1d

⏱️ Time: N/A Space: N/A

Brute Force

⏱️ Time: O(n×k) Space: O(1)

For each possible starting position, extract the k-size subarray and check if all elements are consecutive and ascending. If yes, return the maximum (last) element, otherwise return -1.

Sliding Window with Consecutive Tracking

⏱️ Time: O(n) Space: O(1)

Maintain a count of how many consecutive elements we've seen. As we slide the window, we only need to check if the new element continues the sequence and update our consecutive count accordingly.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int nums[100000];
static int result[100000];

int* findPowerOfKSizeSubarrays(int* nums, int numsSize, int k, int* returnSize) {
    *returnSize = numsSize - k + 1;
    
    for (int i = 0; i <= numsSize - k; i++) {
        // Check if subarray nums[i..i+k-1] is consecutive and sorted
        int isValid = 1;
        
        // Check if consecutive and sorted
        for (int j = i + 1; j < i + k; j++) {
            if (nums[j] != nums[j-1] + 1) {
                isValid = 0;
                break;
            }
        }
        
        if (isValid) {
            result[i] = nums[i + k - 1]; // Maximum element (last element)
        } else {
            result[i] = -1;
        }
    }
    
    return result;
}

int main() {
    char line[1000000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array [1,2,3,4]
    int numsSize = 0;
    char* ptr = line;
    
    // Skip initial whitespace and find '['
    while (*ptr && *ptr != '[') ptr++;
    if (*ptr == '[') ptr++;
    
    // Parse numbers
    while (*ptr && *ptr != ']') {
        while (*ptr == ' ' || *ptr == ',') ptr++;
        if (*ptr >= '0' && *ptr <= '9' || *ptr == '-') {
            nums[numsSize++] = strtol(ptr, &ptr, 10);
        } else {
            ptr++;
        }
    }
    
    // Read k
    int k;
    scanf("%d", &k);
    
    int returnSize;
    int* res = findPowerOfKSizeSubarrays(nums, numsSize, k, &returnSize);
    
    // Print result
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", res[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

✓ Linear Growth

Space Complexity

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen