Problem

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

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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

1
2
3
4


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

Output: [-1,-1]

Example 3

1
2
3
4


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

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

Constraints

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

Solution

Method 1 – Sliding Window and Consecutive Check

Intuition

For each subarray of size k, check if the elements are sorted in ascending order and are consecutive. If so, the power is the maximum element; otherwise, it’s -1. We can use a set to check for duplicates and compare min and max to verify consecutiveness.

Approach

  1. For each window of size k in nums:
    • Check if the subarray is sorted in ascending order.
    • Check if all elements are consecutive (max - min == k - 1 and all unique).
    • If both conditions hold, set power to max element; else, -1.
  2. Collect results for all windows.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    vector<int> getResults(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> ans;
        for (int i = 0; i + k <= n; ++i) {
            bool sorted = true;
            int mn = nums[i], mx = nums[i], prev = nums[i];
            unordered_set<int> st = {nums[i]};
            for (int j = i + 1; j < i + k; ++j) {
                if (nums[j] <= prev) sorted = false;
                mn = min(mn, nums[j]);
                mx = max(mx, nums[j]);
                st.insert(nums[j]);
                prev = nums[j];
            }
            if (sorted && mx - mn == k - 1 && st.size() == k)
                ans.push_back(mx);
            else
                ans.push_back(-1);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func getResults(nums []int, k int) []int {
    n := len(nums)
    ans := []int{}
    for i := 0; i+k <= n; i++ {
        sorted := true
        mn, mx := nums[i], nums[i]
        prev := nums[i]
        st := map[int]struct{}{nums[i]: {}}
        for j := i + 1; j < i+k; j++ {
            if nums[j] <= prev {
                sorted = false
            }
            if nums[j] < mn {
                mn = nums[j]
            }
            if nums[j] > mx {
                mx = nums[j]
            }
            st[nums[j]] = struct{}{}
            prev = nums[j]
        }
        if sorted && mx-mn == k-1 && len(st) == k {
            ans = append(ans, mx)
        } else {
            ans = append(ans, -1)
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public List<Integer> getResults(int[] nums, int k) {
        int n = nums.length;
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i + k <= n; ++i) {
            boolean sorted = true;
            int mn = nums[i], mx = nums[i], prev = nums[i];
            Set<Integer> st = new HashSet<>();
            st.add(nums[i]);
            for (int j = i + 1; j < i + k; ++j) {
                if (nums[j] <= prev) sorted = false;
                mn = Math.min(mn, nums[j]);
                mx = Math.max(mx, nums[j]);
                st.add(nums[j]);
                prev = nums[j];
            }
            if (sorted && mx - mn == k - 1 && st.size() == k)
                ans.add(mx);
            else
                ans.add(-1);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    fun getResults(nums: IntArray, k: Int): List<Int> {
        val n = nums.size
        val ans = mutableListOf<Int>()
        for (i in 0..n - k) {
            var sorted = true
            var mn = nums[i]
            var mx = nums[i]
            var prev = nums[i]
            val st = mutableSetOf(nums[i])
            for (j in i + 1 until i + k) {
                if (nums[j] <= prev) sorted = false
                mn = minOf(mn, nums[j])
                mx = maxOf(mx, nums[j])
                st.add(nums[j])
                prev = nums[j]
            }
            if (sorted && mx - mn == k - 1 && st.size == k)
                ans.add(mx)
            else
                ans.add(-1)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def getResults(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        ans = []
        for i in range(n - k + 1):
            window = nums[i:i+k]
            if all(window[j] > window[j-1] for j in range(1, k)) and max(window) - min(window) == k - 1 and len(set(window)) == k:
                ans.append(max(window))
            else:
                ans.append(-1)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

impl Solution {
    pub fn get_results(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let n = nums.len();
        let k = k as usize;
        let mut ans = vec![];
        for i in 0..=n - k {
            let mut sorted = true;
            let mut mn = nums[i];
            let mut mx = nums[i];
            let mut prev = nums[i];
            let mut st = std::collections::HashSet::new();
            st.insert(nums[i]);
            for j in i + 1..i + k {
                if nums[j] <= prev { sorted = false; }
                mn = mn.min(nums[j]);
                mx = mx.max(nums[j]);
                st.insert(nums[j]);
                prev = nums[j];
            }
            if sorted && mx - mn == (k - 1) as i32 && st.len() == k {
                ans.push(mx);
            } else {
                ans.push(-1);
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    getResults(nums: number[], k: number): number[] {
        const n = nums.length;
        const ans: number[] = [];
        for (let i = 0; i + k <= n; ++i) {
            const window = nums.slice(i, i + k);
            const sorted = window.every((v, j, arr) => j === 0 || v > arr[j - 1]);
            const mn = Math.min(...window);
            const mx = Math.max(...window);
            const st = new Set(window);
            if (sorted && mx - mn === k - 1 && st.size === k) {
                ans.push(mx);
            } else {
                ans.push(-1);
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(nk) — For each window, check k elements.
  • 🧺 Space complexity: O(k) — For the set and window.