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 this problem, consider the conditions that determine the power of each subarray: the subarray must be composed of consecutive and ascending integers. Our task is to efficiently verify these conditions for each possible subarray of length k.

Here's the approach in detail:

1. Tracking Consecutive Subarrays: We use an array f to store the length of consecutive sequences ending at each position i in the nums array. Initially, set each f[i] to 1, as each element alone is a consecutive subarray of length 1.

2. Identify Continuity: Traverse the array nums beginning from the second element. For each element at index i, check if it is one greater than the previous element (nums[i] == nums[i - 1] + 1). If true, update f[i] to f[i - 1] + 1, indicating that the consecutive sequence has extended by one more element.

3. Evaluate Subarrays: After updating f, determine the power of each subarray of length k. For a subarray ending at index i (starting at i - k + 1), if f[i] is at least k, the subarray is a valid consecutive subsequence, and its power is its maximum element, nums[i]. Otherwise, the power is -1.

4. Return the Results: Collect the power of each subarray in an array results and return it.

By systematically tracking the length of consecutive increasing sequences and checking these lengths against k, we can efficiently solve this problem using a single traversal of the array.

Learn more about Sliding Window patterns.

Solution Approach

The solution to the problem is implemented using an algorithm that leverages dynamic programming with the help of an auxiliary array f. Here's a step-by-step breakdown of the approach:

1. Initialize the Auxiliary Array:

   • Create an array f of the same length as nums, where each element is initialized to 1. This array will keep track of the length of the current consecutive sequence ending at each position.

2. Build the Consecutive Sequence Tracker:

   • Iterate through the nums array starting from the second element (index 1). For each element at index i, compare it with the previous element:
     • If nums[i] == nums[i - 1] + 1, it extends the existing consecutive sequence, so update f[i] to f[i - 1] + 1.
     • Otherwise, reset f[i] to 1, indicating the start of a new potential sequence.

3. Calculate Subarray Power:

   • Iterate over the range from k - 1 to n (exclusive). For each index i, calculate the power of the subarray ending at i (which starts at i - k + 1 in nums):
     • If f[i] is greater than or equal to k, the subarray is a valid consecutive sequence, and its power is nums[i].
     • If f[i] is less than k, it means the subarray does not meet the required consecutive and ascending condition, and its power is -1.

4. Return the Result:

   • Construct and return the results array containing the calculated power for each subarray of size k.

The solution efficiently processes the input array in a single pass to build the auxiliary f array, ensuring a time complexity of O(n), where n is the length of the input array nums.

Example Walkthrough

Let's walk through an example to illustrate the solution approach.

Consider the array nums = [1, 2, 4, 5, 6, 8] and k = 3. We want to find the power of all subarrays of size 3.

1. Initialize the Auxiliary Array f:

   • Start with f = [1, 1, 1, 1, 1, 1]. Initially, each element is its own sequence.

2. Build the Consecutive Sequence Tracker:

   • Compare nums[1] = 2 with nums[0] = 1. Since 2 is 1 + 1, update f[1] to 2. Now, f = [1, 2, 1, 1, 1, 1].
   • nums[2] = 4 and nums[1] = 2 are not consecutive, so f[2] stays 1.
   • nums[3] = 5 is 4 + 1, so update f[3] to f[2] + 1 = 2. Resulting in f = [1, 2, 1, 2, 1, 1].
   • nums[4] = 6 is 5 + 1, update f[4] to f[3] + 1 = 3. Now, f = [1, 2, 1, 2, 3, 1].
   • nums[5] = 8 and nums[4] = 6 are not consecutive, so f[5] remains 1.

3. Calculate Subarray Power:

   • For subarray ending at index 2 (nums[0..2] = [1, 2, 4]), f[2] = 1, which is less than k, so power is -1.
   • For subarray ending at index 3 (nums[1..3] = [2, 4, 5]), f[3] = 2, which is less than k, so power is -1.
   • For subarray ending at index 4 (nums[2..4] = [4, 5, 6]), f[4] = 3, which is equal to k, so power is 6.
   • For subarray ending at index 5 (nums[3..5] = [5, 6, 8]), f[5] = 1, which is less than k, so power is -1.

4. Return the Result:

   • Construct results = [-1, -1, 6, -1].

Thus, the power of each subarray of size 3 is [-1, -1, 6, -1].

Solution Implementation

Time and Space Complexity

The code processes the input list nums which has a length of n. The time complexity is determined by the way the list is traversed and modified.

• The loop for i in range(1, n): iterates over the list nums once, performing a constant-time check and possibly updating the list f. Thus, this loop contributes a time complexity of O(n).

• The list comprehension [nums[i] if f[i] >= k else -1 for i in range(k - 1, n)] also iterates through part of nums once, leading to another O(n) operation depending on the values of k and n.

Combining these, the overall time complexity of the code is O(n).

The space complexity is determined by the extra space used:

• The list f is initialized with one element for each element in nums, contributing a space complexity of O(n).

• The output list generated by the list comprehension also holds up to n elements, but it's essentially the answer being output, thus not adding to auxiliary space complexity.

Therefore, the total space complexity remains O(n), as any additional space used is directly proportional to n.

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