Katkat
Back

Minimize Array Amplitude After Removing a Contiguous Block

Hudson River TradingSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Tests array manipulation and prefix/suffix extremum tracking to minimize the spread (max - min) of an array after removing a contiguous subarray of length k.

Minimize Array Amplitude After Removing a Contiguous Block

The amplitude of an array of numbers is defined as the difference between its maximum and minimum elements: max(arr) - min(arr). The amplitude of an array with a single element is 0.

You are given an array of integers nums of length n and an integer k (1 <= k < n). You must remove exactly one contiguous subarray of length k from nums.

Return the minimum possible amplitude of the remaining n - k elements.

Function Signature

def min_amplitude(nums: list[int], k: int) -> int:
    pass

Constraints

  • 2 <= len(nums) <= 200,000
  • 1 <= k < len(nums)
  • -10^9 <= nums[i] <= 10^9

Examples

Example 1:

Input: nums = [3, 5, 1, 3, 9, 8], k = 2
Output: 4
Explanation:
- Remove [3, 5] (indices 0..1): remaining is [1, 3, 9, 8], min = 1, max = 9, amplitude = 8
- Remove [5, 1] (indices 1..2): remaining is [3, 3, 9, 8], min = 3, max = 9, amplitude = 6
- Remove [1, 3] (indices 2..3): remaining is [3, 5, 9, 8], min = 3, max = 9, amplitude = 6
- Remove [3, 9] (indices 3..4): remaining is [3, 5, 1, 8], min = 1, max = 8, amplitude = 7
- Remove [9, 8] (indices 4..5): remaining is [3, 5, 1, 3], min = 1, max = 5, amplitude = 4
The minimum amplitude achieved is 4.

Example 2:

Input: nums = [10, -2, 5, 100], k = 1
Output: 7
Explanation:
Removing nums[3] = 100 leaves [10, -2, 5] with amplitude 10 - (-2) = 12.
Removing nums[1] = -2 leaves [10, 5, 100] with amplitude 100 - 5 = 95.
Removing nums[0] = 10 leaves [-2, 5, 100] with amplitude 100 - (-2) = 102.
Removing nums[2] = 5 leaves [10, -2, 100] with amplitude 102.
Wait, if nums = [10, -2, 5, 100] and k = 2, removing [100] is k=1. The best is removing 100 to get 12.
(For k = 3, removing any 3 elements leaves 1 element, amplitude 0).

Edge Cases

  • k = len(nums) - 1: Exactly one element remains, so amplitude is always 0.
  • Large values and negative integers: Ensure logic handles negative bounds correctly.

Hints

Hint 1

When a block nums[i : i + k] is removed, the remaining elements are formed by the prefix nums[0 : i] and suffix nums[i + k : n].

Hint 2

To compute the amplitude of the remaining elements in O(1) for a fixed removal window, you need the minimum and maximum of both the prefix and the suffix.

Hint 3

Precompute prefix min/max and suffix min/max arrays so you can evaluate all possible starting indices i in a single linear pass.

Follow-up questions

  • Can you reduce the auxiliary space to O(1) beyond storing the input array?
  • How would you solve the problem if you could remove a contiguous block of length *at most* k rather than *exactly* k?
  • How would you approach the problem if you were allowed to remove two non-overlapping contiguous blocks of lengths k1 and k2?