• Leetcode POTDs

Problem 3255 Find the Power of K-Size Subarrays II

Problem Statement

Link - Problem 3255

Question

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

Example 1:

Example 2:

Example 3:

Constraints:

• 1 <= n == nums.length <= 105
• 1 <= nums[i] <= 106
• 1 <= k <= n

Solution

class Solution {
public:
    vector<int> resultsArray(const vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> result(n - k + 1, -1);
        deque<int> dq;

        vector<int> diff(n - 1);
        for (int i = 0; i < n - 1; ++i) {
            diff[i] = nums[i + 1] - nums[i];
        }


        int consecutive_count = 0;
        for (int i = 0; i < k - 1; ++i) {
            if (diff[i] == 1) consecutive_count++;
        }

        for (int i = 0; i < n; ++i) {

            if (!dq.empty() && dq.front() <= i - k) {
                dq.pop_front();
            }

            while (!dq.empty() && nums[i] >= nums[dq.back()]) {
                dq.pop_back();
            }
            dq.push_back(i);

            if (i >= k - 1) {
                if (consecutive_count == k - 1) {
                    result[i - k + 1] = nums[dq.front()];
                }

                if (i - k + 1 < n - 1) {
                    if (diff[i - k + 1] == 1) consecutive_count--;
                    if (i < n - 1 && diff[i] == 1) consecutive_count++;
                }
            }
        }

        return result;
    }
};

Complexity Analysis

| Algorithm                 | Time Complexity | Space Complexity |
| ------------------------- | --------------- | ---------------- |
| Sliding Window with Deque | O(n)            | O(n)             |

Explanation

Intial Thoughts

My initial approach would be to identify that checking every subarray for being consecutive and sorted would result in O(n^2 log n) complexity which is inefficient for large inputs. I’d also think that the key here lies in finding a relation between each subarray. Then, consider using some sort of caching to reduce the number of computations required, for example the difference array, and a deque to keep track of maximum elements for each subarray. Consider starting by identifying when a subarray is a contiguous sequence of numbers and use the information from the last subarray to efficiently calculate the next one.

Intuitive Analysis

To intuitively solve the problem, notice that all you need to do is keep track of whether the differences between the current subarray’s elements are always equal to 1 and also track the max element for each subarray in O(1) time. After you’ve found the first subarray that’s a contiguous sequence, then notice that adding one element and removing another for the next subarray would only change the result by adding one or removing one element from the consecutive count if the differences are 1. To further optimize the algorithm, consider that each subarray’s max value must also be calculated in O(1) time. You can use a deque for this, it’s similar to a sliding window approach in other problems, where the deque holds the indices of elements in the current subarray, ordered by the value at each index, from largest to smallest. This way, you’re always able to find the max element in O(1) time and be able to efficiently calculate the max of the next subarray.

1. Intuition

• The problem requires finding the power of all subarrays of size k in the given array nums.
• The power of an array is defined as its maximum element if all elements are consecutive and sorted in ascending order, otherwise -1.
• To solve this problem, we need to check each subarray of size k and determine if its elements are consecutive and sorted.
• We can use a deque to keep track of the indices of the elements in the current subarray.
• We also need to keep track of the count of consecutive elements in the current subarray.
• If the count of consecutive elements is equal to k-1, then the subarray is consecutive and sorted, and we can update the result array.
• We can use a diff array to store the differences between consecutive elements in the nums array.
• We can iterate over the nums array and update the consecutive count and the result array accordingly.

2. Implementation

• We initialize a result array of size n-k+1 with all elements set to -1.
• We create a deque dq to store the indices of the elements in the current subarray.
• We create a diff array to store the differences between consecutive elements in the nums array.
• We iterate over the nums array and update the consecutive count and the result array accordingly.
• We use the line if (diff[i] == 1) consecutive_count++; to update the consecutive count.
• We use the line if (consecutive_count == k - 1) result[i - k + 1] = nums[dq.front()]; to update the result array.
• We use the line while (!dq.empty() && nums[i] >= nums[dq.back()]) dq.pop_back(); to update the deque.
• We return the result array at the end of the function.

Complexity Analysis

Time Complexity:

• The code has two major loops: one for creating the diff vector and the other for processing the deque and calculating results. Both loops run in linear time.
• Dominant operations are loop iterations and deque operations (pop_front, pop_back, and push_back). Since each element is processed at most twice (once in each loop and additional constant time operations), the time complexity is linear.
• The overall time complexity is O(n) due to n being the maximum number of iterations in both loops, where n is the size of the input vector nums.

Space Complexity:

• The code uses additional data structures, including the diff vector, the dq deque, and the result vector. All these data structures have a size dependent on the input size n.
• The impact of the diff vector and the result vector on space complexity is O(n) since their size grows linearly with the input size n.
• The dq deque also has a maximum size of n, as it stores at most n indices of the input vector. Therefore, the overall space complexity is O(n) due to these additional data structures.

Footnote

This question is rated as Medium difficulty.

Hints

Let dp[i] denote the length of the longest subarray ending at index i that has consecutive and sorted elements.

Use a TreeMap with a sliding window to check if there are k elements in the subarray ending at index i.

If TreeMap has less than k elements and dp[i] < k, the subarray has power equal to -1.

Is it possible to achieve O(nums.length) using a Stack?

Similar Questions: