• Leetcode POTDs

Problem 3254 Find the Power of K-Size Subarrays I

Problem Statement

Link - Problem 3254

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 <= 500
• 1 <= nums[i] <= 105
• 1 <= k <= n

Solution

class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        if(k==1)
            return nums;

        int size = nums.size();
        vector<int>result(size-k+1,-1);
        int count = 1;
        for(int i=0;i<size-1;i++){

            if(nums[i]+1 == nums[i+1])
                count++;
            else
                count =1;

            if(count >= k)
                result[i+2-k] = nums[i+1];
        }
        return result;

    }
};

Complexity Analysis

| Algorithm                                  | Time Complexity | Space Complexity |
| ------------------------------------------ | --------------- | ---------------- |
| Single-pass traversal with auxiliary array | O(n)            | O(n)             |

Explanation

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 sliding window approach to efficiently check all subarrays of size k.
• We need to keep track of the count of consecutive elements in the current window.
• If the count is greater than or equal to k, we can update the result array with the maximum element of the current window.
• We need to handle the edge case where k is 1, in which case the result is simply the input array.

2. Implementation

• The function resultsArray takes a vector of integers nums and an integer k as input and returns a vector of integers.
• If k is 1, the function returns the input array nums.
• The function initializes a result vector of size n-k+1 with all elements set to -1.
• The function uses a for loop to iterate over the input array, keeping track of the count of consecutive elements.
• Inside the loop, the function checks if the current element is consecutive to the previous element by comparing nums[i] and nums[i+1].
• If the elements are consecutive, the function increments the count; otherwise, it resets the count to 1.
• If the count is greater than or equal to k, the function updates the result array with the maximum element of the current window.

Complexity Analysis

Time Complexity:

• The solution iterates over the input array nums once, with a single loop running from i=0 to size-2
• The dominant operation is the conditional increment of the count variable, which occurs once per iteration, resulting in O(n) time complexity
• The time complexity remains the same in the best, average, and worst cases as the input size n directly dictates the number of iterations

Space Complexity:

• The solution creates an auxiliary array result of size n-k+1, where n is the size of the input array
• The space complexity is dominated by the storage required for the result array, leading to O(n) space complexity
• The space complexity remains the same in all cases as the size of the auxiliary array directly depends on the input size, which must be stored in memory

Footnote

This question is rated as Medium difficulty.

Hints

Can we use a brute force solution with nested loops and HashSet?

Similar Questions: