mediumArraysPattern: Basic Traversal
Maximum Absolute Variance Solution
Problem Statement
Given an integer array nums of length n, define the variance of any two elements at indices i and j as |nums[i] - nums[j]|. Your objective is to find the maximum possible variance such that the difference between the indices is at least k, represented as |i - j| >= k. Return the maximum variance found across all valid pairs of indices.
Examples
Example 1:
Input:nums = [1, 5, 2, 8, 3], k = 3
Output:7
Explanation: The valid pairs (i, j) with index difference at least 3 are (0, 3), (0, 4), and (1, 4). The pairs yield values |1-8|=7, |1-3|=2, and |5-3|=2, respectively, with 7 being the maximum.
Example 2:
Input:nums = [10, 2, 5, 1, 9], k = 2
Output:9
Explanation: Comparing index 0 (value 10) and index 3 (value 1), the absolute difference is |10-1|=9. Since the index difference 3 >= 2, this is a valid pair.
Constraints
- 2 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9
- 1 <= k < nums.length
Time: O(n) Space: O(1)
The optimized approach uses a single-pass greedy technique with prefix tracking. As we iterate through the array starting from index i = k, the set of allowed indices for comparison is [0...i-k]. We maintain the running minimum and maximum values of this prefix in O(1) auxiliary space, allowing us to find the maximum possible variance for each index i in constant time.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
from typing import List
class Solution:
def max_absolute_variance(self, nums: List[int], k: int) -> int:
if not nums or k >= len(nums):
return 0
max_var = 0
min_prefix = nums[0]
max_prefix = nums[0]
for i in range(k, len(nums)):
min_prefix = min(min_prefix, nums[i - k])
max_prefix = max(max_prefix, nums[i - k])
max_var = max(max_var, abs(nums[i] - min_prefix), abs(nums[i] - max_prefix))
return max_var