Maximum Absolute Variance — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Iterating arrays and tracking min/max
O(n)O(1)Problem Description
Given an integer array nums of length n and an integer k, find the maximum possible variance such that the difference between the indices is at least k.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Maximum Absolute Variance"
WHY DOES IT MATTER?
This pattern—maintaining running extremal values over a sliding distance—is fundamental for many "best‑pair" problems where a positional constraint exists. Recognizing that the optimal partner for any element is either the smallest or largest element seen far enough back (or ahead) lets you avoid quadratic enumeration and directly compute the answer in linear time.
OPTIMIZATION CHALLENGE
The key insight is that the absolute difference decomposes into two directional cases, allowing you to treat the problem as two independent maximization sub‑problems (max - min and min - max). By updating a single running min and max that respect the k‑distance rule, you collapse an O(n²) search space into O(n).
REAL-WORLD CONNECTION
Think of a distributed cache that must serve read‑through requests with a freshness window of k seconds. To decide the most stale versus most fresh entry within that window, you keep track of the earliest (minimum timestamp) and latest (maximum timestamp) entries as new requests arrive, analogous to the min/max sliding window used here.
During an interview, compute the forward‑pass min‑prefix and max‑prefix simultaneously; this not only halves the code but also demonstrates to the interviewer that you understand the symmetry of the problem and can write concise, bug‑free logic.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem asks for the largest absolute difference between any two elements whose indices are separated by at least k positions. A naïve double‑loop enumerates every pair (i, j) with |i‑j| ≥ k, leading to O(n²) time, which quickly becomes infeasible for n up to 10⁵ or higher. The optimal paradigm leverages the fact that the absolute difference can be expressed as either (nums[i] - nums[j]) or (nums[j] - nums[i]). By scanning the array once while remembering the minimum (or maximum) value seen at a distance of at least k, we can compute the best candidate for each position in O(1) amortized time. This sliding‑window extremum technique is a classic example of prefix‑suffix aggregation: for each index i we need the best value among indices ≤ i‑k (or ≥ i+k). Maintaining two running aggregates—minimum and maximum—accomplishes this without extra passes, yielding a linear‑time solution.
The optimal solution therefore consists of two linear scans. In the forward pass we keep track of the smallest element encountered at least k steps before the current index; the candidate variance is |nums[i] - minSoFar|. In the backward pass we keep the largest element seen at least k steps after the current index; the candidate variance is |maxSoFar - nums[i]|. The maximum of all candidates across both passes is the answer. This approach reduces both time and auxiliary space to O(n) and O(1) respectively, making it suitable for large‑scale inputs.
Why this works hinges on the monotonic property of min and max: once a value becomes the minimum (or maximum) for a window, it remains optimal for any later index until it slides out of the k‑distance window. Thus we never need to recompute from scratch, and the algorithm gracefully handles negative numbers, duplicates, and large ranges.
Interview Questions on This Problem
Q1How would you modify the solution if the constraint changed from "at least k" to "exactly k" distance between indices?
Maintain two sliding windows of size 1: one that stores the element at i‑k and another that stores the element at i+k as you iterate. For each i, compute |nums[i] - nums[i‑k]| and |nums[i] - nums[i+k]| (when those indices exist) and keep the global maximum. This still runs in O(n) time and O(1) space.
Q2Can you solve the problem in a single pass without a backward scan?
Yes. While moving left‑to‑right, keep both the minimum and maximum of the prefix that is at least k behind the current index. For each i, evaluate both |nums[i] - minPrefix| and |maxPrefix - nums[i]|. The maximum of these values over the whole scan yields the answer, eliminating the need for a separate backward pass.
Q3What would be the impact on time/space complexity if the array were streamed and you could only store O(k) elements at any time?
The algorithm already needs only O(1) extra memory beyond the input, which satisfies the O(k) restriction for any k ≥ 1. The streaming version would keep a circular buffer of the last k elements to know when a value exits the valid window, but the core min/max aggregates remain constant‑space, preserving O(n) time.
Examples
Input
[1, 2, 3, 4, 5]
Output
2
Explanation: Step-by-step: Given array [1, 2, 3, 4, 5] and k = 2, we can calculate the variance by considering the subarrays [1, 2, 3] and [3, 4, 5]. The maximum variance is then calculated as the difference between the maximum and minimum values in these subarrays, which is 2.
Input
[10, 20, 30, 40, 50]
Output
20
Explanation: Step-by-step: Given array [10, 20, 30, 40, 50] and k = 3, we can calculate the variance by considering the subarrays [10, 20, 30] and [30, 40, 50]. The maximum variance is then calculated as the difference between the maximum and minimum values in these subarrays, which is 20.
Constraints
- 2 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9
- 1 <= k < nums.length
Optimal Approach & Strategy
Do a single linear scan while keeping the minimum and maximum values seen at least k indices earlier; update the answer with the absolute differences to the current element.
Brute Force Approach
Check every pair (i, j) with |i‑j| ≥ k and compute |nums[i]‑nums[j]|, keeping the maximum.
Code Solutions
function solution(nums, k) {
let n = nums.length;
let maxVariance = -Infinity;
for (let i = 0; i <= n - k; i++) {
let subarray = nums.slice(i, i + k);
let min = Math.min(...subarray);
let max = Math.max(...subarray);
let variance = max - min;
maxVariance = Math.max(maxVariance, variance);
}
return maxVariance;
}class Solution {
public:
int solution(vector<int>& nums, int k) {
int n = nums.size();
int maxVariance = INT_MIN;
for (int i = 0; i <= n - k; i++) {
vector<int> subarray(nums.begin() + i, nums.begin() + i + k);
int min = *min_element(subarray.begin(), subarray.end());
int max = *max_element(subarray.begin(), subarray.end());
int variance = max - min;
maxVariance = max(maxVariance, variance);
}
return maxVariance;
}
};class Solution {
public int solution(int[] nums, int k) {
int n = nums.length;
int maxVariance = Integer.MIN_VALUE;
for (int i = 0; i <= n - k; i++) {
int[] subarray = Arrays.copyOfRange(nums, i, i + k);
int min = Arrays.stream(subarray).min().getAsInt();
int max = Arrays.stream(subarray).max().getAsInt();
int variance = max - min;
maxVariance = Math.max(maxVariance, variance);
}
return maxVariance;
}
}def solution(nums, k):
n = len(nums)
max_variance = float('-inf')
for i in range(n - k + 1):
subarray = nums[i:i + k]
min_val = min(subarray)
max_val = max(subarray)
variance = max_val - min_val
max_variance = max(max_variance, variance)
return max_variancefunction solution(nums, k) {
let n = nums.length;
let maxVariance = -Infinity;
for (let i = 0; i <= n - k; i++) {
let subarray = nums.slice(i, i + k);
let min = Math.min(...subarray);
let max = Math.max(...subarray);
let variance = max - min;
maxVariance = Math.max(maxVariance, variance);
}
return maxVariance;
}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.