Python – Minimize the Maximum Difference Between Heights in an Array

In many DSA interviews, you may be asked to solve the problem of minimizing the maximum difference between heights after adjusting each height by adding or subtracting a given value K. This tutorial will explain the problem, provide sample inputs and outputs, walk through the solution steps, and present a complete Python program.

Problem Statement

Given an array arr of heights and an integer K, you can increase or decrease each height by K (only once per element). The goal is to minimize the difference between the maximum and minimum heights after these modifications. The result is the minimized maximum difference.

Sample Input and Output

Example 1:

</>
Copy
Input: arr = [1, 15, 10], K = 6
Output: 5

Example 2:

</>
Copy
Input: arr = [4, 6, 3, 8, 10], K = 2
Output: 3

Solution Approach

The approach to solve this problem is as follows:

  1. Sort the Array: Sorting the array helps in easily determining the potential minimum and maximum values after modification.
  2. Initial Difference: Compute the initial difference between the largest and smallest elements before any modifications.
  3. Determine Initial Potential Values:
    • Set small = arr[0] + K (the smallest possible height after increasing the smallest element).
    • Set large = arr[-1] - K (the largest possible height after decreasing the largest element).
  4. Iterate through the Array: For each index from 0 to n-2, calculate:
    1. min_val = min(small, arr[i+1] - K)
    2. max_val = max(large, arr[i] + K)
    Update the answer with the minimum difference found, max_val - min_val.

This method ensures that we consider the optimal way to adjust each height so that the overall difference is minimized, while processing the sorted array in a systematic manner.

Python Program

</>
Copy
def minimize_max_difference(arr, k):
    # Sort the array to process heights in order
    arr.sort()
    
    n = len(arr)
    # Initial maximum difference without any modifications
    answer = arr[-1] - arr[0]
    
    # If there's only one element, no difference exists
    if n == 1:
        return 0

    # Set initial smallest and largest possible values after modification
    small = arr[0] + k
    large = arr[-1] - k

    # Swap if small becomes larger than large
    if small > large:
        small, large = large, small

    # Traverse through the array to find the minimum difference
    for i in range(n - 1):
        min_val = min(small, arr[i + 1] - k)
        max_val = max(large, arr[i] + k)
        answer = min(answer, max_val - min_val)
    
    return answer

# Example 1
arr1 = [1, 15, 10]
k1 = 6
print("Minimized Maximum Difference:", minimize_max_difference(arr1, k1))
# Expected Output: 5

# Example 2
arr2 = [4, 6, 3, 8, 10]
k2 = 2
print("Minimized Maximum Difference:", minimize_max_difference(arr2, k2))
# Expected Output: 3

Conclusion

This tutorial explained how to minimize the maximum difference between heights in an array by modifying each height with a given value K. We discussed the problem, provided sample inputs/outputs, explained the solution approach step-by-step, and presented a complete Python program.