Consecutive Maximum Values — Problem Statement & Solution Guide
Problem Description
Given an array of integers values and an integer windowSize, find the maximum value in every subarray of size windowSize. If the input array contains non-integer values, throw an error. If the window size is larger than the array size, return an empty array.
Examples
Input
[1, 2, 3, 4, 5], 3
Output
[3, 4, 5]
Explanation: Step-by-step: with input [1, 2, 3, 4, 5] and window size 3, we consider subarrays [1, 2, 3], [2, 3, 4], [3, 4, 5]. The maximum values are 3, 4, 5 respectively, giving output [3, 4, 5].
Input
[10, 20, 30, 40, 50], 1
Output
[10, 20, 30, 40, 50]
Explanation: Step-by-step: with input [10, 20, 30, 40, 50] and window size 1, we consider subarrays [10], [20], [30], [40], [50]. The maximum values are 10, 20, 30, 40, 50 respectively, giving output [10, 20, 30, 40, 50].
Constraints
- 1 <= n <= 10^5
- 1 <= k <= n
- -10^4 <= arr[i] <= 10^4
Optimal Approach & Strategy
Use Deque. Store indices. Remove indices out of window bounds. Remove indices whose values are <= current value (they can never be max). Add current index. Deque front always holds max for current window. Time O(N), Space O(K).
Brute Force Approach
Find max for every window linearly. Time O(N*K).
Verified Code Solutions
function solution(values, windowSize) {
if (values.some(val => typeof val !== 'number')) {
throw new Error('Input array contains non-integer values');
}
if (windowSize > values.length) {
return [];
}
const result = [];
for (let i = 0; i <= values.length - windowSize; i++) {
const subarray = values.slice(i, i + windowSize);
result.push(Math.max(...subarray));
}
return result;
}class Solution {
public:
vector<int> solution(vector<int>& values, int windowSize) {
if (windowSize > values.size()) {
return {};
}
vector<int> result;
for (int i = 0; i <= values.size() - windowSize; i++) {
int max = INT_MIN;
for (int j = i; j < i + windowSize; j++) {
max = std::max(max, values[j]);
}
result.push_back(max);
}
return result;
}
};class Solution {
public int[] solution(int[] values, int windowSize) {
if (windowSize > values.length) {
return new int[0];
}
int[] result = new int[values.length - windowSize + 1];
for (int i = 0; i <= values.length - windowSize; i++) {
int max = Integer.MIN_VALUE;
for (int j = i; j < i + windowSize; j++) {
max = Math.max(max, values[j]);
}
result[i] = max;
}
return result;
}
}def solution(values, windowSize):
if not all(isinstance(val, int) for val in values):
raise ValueError('Input array contains non-integer values')
if windowSize > len(values):
return []
result = []
for i in range(len(values) - windowSize + 1):
subarray = values[i:i + windowSize]
result.append(max(subarray))
return resultfunction solution(values, windowSize) {
if (values.some(val => typeof val !== 'number')) {
throw new Error('Input array contains non-integer values');
}
if (windowSize > values.length) {
return [];
}
const result = [];
for (let i = 0; i <= values.length - windowSize; i++) {
const subarray = values.slice(i, i + windowSize);
result.push(Math.max(...subarray));
}
return result;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.