3254. Find the Power of K-Size Subarrays I

MediumArraySliding Window

Leetcode Link

Problem Description

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

Intuition

To solve the problem, we first need to determine if each subarray of size k within nums consists of consecutive elements in ascending order. The solution makes use of an auxiliary array f which helps in tracking the length of the current consecutive increasing elements.

Auxiliary Array Initialization: We initialize an array f of the same length as nums, where each element is set to 1. This array helps in storing the length of consecutive increasing integers ending at each position in nums.
Building Consecutive Lengths: While iterating through nums, if the current element is exactly 1 more than the previous one (nums[i] == nums[i - 1] + 1), it means the streak of consecutive numbers continues, and we increment the consecutive length count (f[i] = f[i - 1] + 1). Otherwise, the streak is broken, so we reset f[i] to 1.
Determine Subarray Power: For each subarray defined by its end index i (starting from k - 1 to n), we check if it forms a sequence of at least k consecutive numbers by verifying if f[i] is greater than or equal to k. If true, the power is the maximum number of this ascending sequence, which is nums[i]. If not, we assign -1 to denote the subarray doesn’t satisfy the condition.
Return Results: Ultimately, we construct an array capturing the power of each k-sized subarray and return it.

The approach efficiently tracks the consecutive sequences and utilizes the established conditions to determine the power with minimum computations.

Learn more about Sliding Window patterns.

Solution Approach

The solution approach described can be implemented through the following steps and considerations:

Array f Initialization: We start by initializing an array f where f[i] represents the length of the increasing consecutive subsequence that ends at index i of nums. Initially, each entry in f is set to 1 because the smallest possible increasing subsequence includes the element itself.
```
f = [1] * n  # Where n is the length of nums
```

Constructing the f Array: We iterate through the nums array starting from index 1 to n-1. The comparison condition nums[i] == nums[i - 1] + 1 is checked to determine if the current number continues the ascending sequence with the previous number. If true, we increment f[i] by f[i - 1] + 1; otherwise, it remains 1.

for i in range(1, n):
    if nums[i] == nums[i - 1] + 1:
        f[i] = f[i - 1] + 1
    else:
        f[i] = 1

Building the Results: We create a list comprehension to build the resulting array. The iteration starts from k - 1 to n, checking if f[i] is at least k. If the condition holds, the power (maximum element) is nums[i] since it represents the end of a valid k-length consecutive subsequence. If not, we place -1 to indicate the subarray doesn’t qualify.
```
results = [nums[i] if f[i] >= k else -1 for i in range(k - 1, n)]
```
Return the Results: The final step involves returning the results array, capturing the power of each valid subarray of size k.

The overall approach efficiently processes the array with a single pass to determine consecutive subsequences and leverages this information to quickly evaluate each subarray's power, maintaining an optimal time complexity.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach:

Suppose we have an array nums = [3, 4, 5, 6, 1, 2] and k = 3.

Step 1: Auxiliary Array Initialization

We initialize an auxiliary array f with the same length as nums, where each element is set to 1. This array will help track the lengths of increasing consecutive subsequences ending at each index in nums.

f = [1, 1, 1, 1, 1, 1]

Step 2: Constructing the f Array

Now, we iterate through nums starting from index 1:

At index 1, nums[1] = 4 and nums[0] = 3. Since 4 is 3 + 1, we increment f[1] = f[0] + 1 = 2, resulting in f = [1, 2, 1, 1, 1, 1].
At index 2, nums[2] = 5 and nums[1] = 4. Since 5 is 4 + 1, we increment f[2] = f[1] + 1 = 3, resulting in f = [1, 2, 3, 1, 1, 1].
At index 3, nums[3] = 6 and nums[2] = 5. Since 6 is 5 + 1, we increment f[3] = f[2] + 1 = 4, resulting in f = [1, 2, 3, 4, 1, 1].
At index 4, nums[4] = 1 and nums[3] = 6. Since 1 is not 6 + 1, we reset f[4] = 1, resulting in f = [1, 2, 3, 4, 1, 1].
At index 5, nums[5] = 2 and nums[4] = 1. Since 2 is 1 + 1, we increment f[5] = f[4] + 1 = 2, resulting in f = [1, 2, 3, 4, 1, 2].

Step 3: Building the Results

We construct a list comprehension to build the results array. The iteration starts from k - 1 (which is 2 for our example) to n:

At index 2, f[2] = 3 which is greater than or equal to k, so results[0] = nums[2] = 5.
At index 3, f[3] = 4 which is greater than or equal to k, so results[1] = nums[3] = 6.
At index 4, f[4] = 1 which is less than k, so results[2] = -1.
At index 5, f[5] = 2 which is less than k, so results[3] = -1.

results = [5, 6, -1, -1]

Step 4: Return the Results

Finally, we return the results array, which is [5, 6, -1, -1], representing the power of each k-sized subarray of nums.

Solution Implementation

1from typing import List
2
3class Solution:
4    def resultsArray(self, nums: List[int], k: int) -> List[int]:
5        n = len(nums)
6        f = [1] * n  # Initialize an array to keep track of consecutive sequences
7
8        # Iterate through the list and record the length of consecutive increasing sequences
9        for i in range(1, n):
10            if nums[i] == nums[i - 1] + 1:
11                f[i] = f[i - 1] + 1
12
13        # Build the result array with elements meeting the required sequence length, rest are -1
14        return [nums[i] if f[i] >= k else -1 for i in range(k - 1, n)]
15

1import java.util.Arrays;
2
3class Solution {
4    public int[] resultsArray(int[] nums, int k) {
5        int n = nums.length;
6        int[] f = new int[n]; // Array to store lengths of consecutive subarrays
7        Arrays.fill(f, 1); // Initialize all elements in f to 1
8      
9        // Build the 'f' array by checking for consecutive numbers
10        for (int i = 1; i < n; ++i) {
11            if (nums[i] == nums[i - 1] + 1) {
12                f[i] = f[i - 1] + 1; // Increment length if consecutive
13            }
14        }
15      
16        int[] ans = new int[n - k + 1]; // Array to store results
17        // Fill the result array with either the last number of a valid subarray or -1
18        for (int i = k - 1; i < n; ++i) {
19            ans[i - k + 1] = f[i] >= k ? nums[i] : -1;
20        }
21      
22        return ans;
23    }
24}
25

1#include <vector>
2
3class Solution {
4public:
5    std::vector<int> resultsArray(std::vector<int>& nums, int k) {
6        int n = nums.size();
7
8        // Array to store the length of consecutive increasing subsequence ending at each index
9        int consecutiveLengths[n];
10        consecutiveLengths[0] = 1; // Initializing the first element's length as 1
11
12        // Calculate the length of consecutive increasing subsequences
13        for (int i = 1; i < n; ++i) {
14            if (nums[i] == nums[i - 1] + 1) {
15                consecutiveLengths[i] = consecutiveLengths[i - 1] + 1; // Increase length if consecutive
16            } else {
17                consecutiveLengths[i] = 1; // Reset length if not consecutive
18            }
19        }
20
21        std::vector<int> ans; // Vector to store the final results
22
23        // Determine which elements are valid according to the condition
24        for (int i = k - 1; i < n; ++i) {
25            if (consecutiveLengths[i] >= k) {
26                ans.push_back(nums[i]); // Element is valid, append to the result
27            } else {
28                ans.push_back(-1); // Element does not meet the requirement, append -1
29            }
30        }
31
32        return ans;
33    }
34};
35

1// This function takes an array of numbers `nums` and an integer `k`, returning an array of numbers.
2function resultsArray(nums: number[], k: number): number[] {
3    const n = nums.length; // Store the length of the input array.
4  
5    // Initialize an array `f` filled with 1s, where `f[i]` keeps track of consecutive elements.
6    const f: number[] = Array(n).fill(1);
7  
8    // Iterate through `nums` starting from the second element.
9    for (let i = 1; i < n; ++i) {
10        // Check if the current element is consecutive to the previous.
11        if (nums[i] === nums[i - 1] + 1) {
12            // Increment the current position by previous count if consecutive.
13            f[i] = f[i - 1] + 1;
14        }
15    }
16  
17    // Result array `ans` to store the desired output.
18    const ans: number[] = [];
19  
20    // Start from the (k-1)th element since we need at least k elements in a sequence.
21    for (let i = k - 1; i < n; ++i) {
22        // If the length of consecutive numbers ending at `i` is at least `k`, include `nums[i]`.
23        // Otherwise, include `-1`.
24        ans.push(f[i] >= k ? nums[i] : -1);
25    }
26  
27    // Return the constructed result array.
28    return ans;
29}
30

Time and Space Complexity

The time complexity of the provided code is O(n). This is because the algorithm involves iterating over the array nums twice. The first loop computes the values in the auxiliary array f for each element, resulting in a linear pass over the input of size n. The second loop creates the result using these values, also covering the entire array once.

The space complexity is O(n). This is due to the storage of the auxiliary array f, which holds an integer for each element in nums, leading to a total space requirement proportional to the input size.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

How does merge sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Merge sort does not use divide and conquer

I don’t know