Find the Power of K-Size Subarrays I
Find the Power of K-Size Subarrays I is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Fixed Size (Subarray Calculation) subpattern.
Problem statement
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
Topics and companies
Topics: Array, Sliding Window.
How to practise Find the Power of K-Size Subarrays I on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Find the Power of K-Size Subarrays I in the code editor, or read the Find the Power of K-Size Subarrays I editorial for a worked solution with its approach and complexity analysis.
Where Find the Power of K-Size Subarrays I sits in the DSA pattern sheet
- Sliding Window pattern guide
- Fixed Size (Subarray Calculation) subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Find the Power of K-Size Subarrays I
Other problems that use the same Fixed Size (Subarray Calculation) and Sliding Window techniques:
- Calculate Compressed Mean — Easy, same subpattern
- Find X-Sum of All K-Long Subarrays I — Easy, same subpattern
- Maximum Average Subarray I — Easy, same subpattern
- Moving Average from Data Stream — Easy, same subpattern
- Contains Duplicate II — Easy, same pattern
- Continuous Subarrays — Medium, same pattern