LeetCode 3254 Find the Power of K-Size Subarrays I

Table of contents

Description

Question Links: LeetCode 3254

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:

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

Output: [3,4,-1,-1,-1]

Explanation:

There are 5 subarrays of nums of size 3:

[1, 2, 3] with the maximum element 3.
[2, 3, 4] with the maximum element 4.
[3, 4, 3] whose elements are not consecutive.
[4, 3, 2] whose elements are not sorted.
[3, 2, 5] whose elements are not consecutive.
Example 2:

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

Output: [-1,-1]

Example 3:

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

Output: [-1,3,-1,3,-1]

 

Constraints:

1 <= n == nums.length <= 500
1 <= nums[i] <= 10^5
1 <= k <= n

Hint 1

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

Solution

Idea

We can maintain a counter of the streak for the consecutive elements seen in the array as we iterate. When the streak reaches k, we can start writing the element (max element of the streak (length k)) to the result as long as the streak is >= k.

Complexity: Time O(n), Space O(1).

Java

class Solution {
    public int[] resultsArray(int[] nums, int k) {
        if (k == 1) return nums; // every single element is a valid subarray
        int n = nums.length, res[] = new int[n - k + 1];
        Arrays.fill(res, -1); // Initialize results to -1
        for (int i = 0, streak = 1; i < n - 1; i++) {
            if (nums[i] + 1 == nums[i + 1]) streak++;
            else streak = 1;
            if (streak >= k) res[i - k + 2] = nums[i + 1];
        }
        return res;
    }
}

C++

class PowerKSizeSubArraysI {
public:
    vector<int> resultsArray(vector<int> &nums, int k) {
        if (k == 1) return nums;
        int n = nums.size();
        vector<int> res(n - k + 1, -1);
        int streak = 1;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] + 1 == nums[i + 1]) streak++;
            else streak = 1;
            if (streak >= k) res[i - k + 2] = nums[i + 1];
        }
        return res;
    }
};

Python

class Solution:
    def resultsArray(self, nums: List[int], k: int) -> List[int]:
        """O(n) time, O(1) space."""
        if k == 1:
            return nums
        n = len(nums)
        res = [-1] * (n - k + 1)
        streak = 1
        for i in range(n - 1):
            if nums[i] + 1 == nums[i + 1]:
                streak += 1
            else:
                streak = 1
            if streak >= k:
                res[i - k + 2] = nums[i + 1]
        return res

Rust

impl Solution {
    pub fn results_array(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let k = k as usize;
        if k == 1 { return nums; }
        let n = nums.len();
        let mut res = vec![-1i32; n - k + 1];
        let mut streak = 1usize;
        for i in 0..n - 1 {
            if nums[i] + 1 == nums[i + 1] { streak += 1; }
            else { streak = 1; }
            if streak >= k { res[i + 2 - k] = nums[i + 1]; }
        }
        res
    }
}