Minimize the Maximum Difference Between Heights

Understanding the Problem

The goal is to minimize the maximum difference between the heights of towers after modifying them within a given range.

Method 1: Sorting and Greedy Approach

This method sorts the array and then modifies heights by either increasing or decreasing within the given range.

import sys

def minimize_difference(arr, k):
    arr.sort()
    n = len(arr)
    min_diff = arr[-1] - arr[0]
    for i in range(1, n):
        min_height = min(arr[0] + k, arr[i] - k)
        max_height = max(arr[-1] - k, arr[i - 1] + k)
        min_diff = min(min_diff, max_height - min_height)
    return min_diff

arr = [1, 15, 10]
k = 6
print("Minimum difference:", minimize_difference(arr, k))
            

Output:

Minimum difference: 5

Method 2: Brute Force

This method tries all possibilities of adding or subtracting k from each element.

from itertools import product

def find_min_difference(arr, k):
    n = len(arr)
    min_diff = float('inf')
    for signs in product([-1, 1], repeat=n):
        modified_arr = [arr[i] + signs[i] * k for i in range(n)]
        min_height = min(modified_arr)
        max_height = max(modified_arr)
        min_diff = min(min_diff, max_height - min_height)
    return min_diff

arr = [1, 15, 10]
k = 6
print("Minimum difference:", find_min_difference(arr, k))
            

Output:

Minimum difference: 5

Method 3: Optimized Sorting Approach

An optimized approach that modifies heights while iterating through the sorted array.

def get_minimized_difference(arr, k):
    arr.sort()
    n = len(arr)
    min_diff = arr[-1] - arr[0]
    smallest, largest = arr[0] + k, arr[-1] - k
    if smallest > largest:
        smallest, largest = largest, smallest
    
    for i in range(1, n - 1):
        decrease = arr[i] - k
        increase = arr[i] + k
        if decrease >= smallest or increase <= largest:
            continue
        if largest - decrease <= increase - smallest:
            smallest = decrease
        else:
            largest = increase
    
    return min(min_diff, largest - smallest)

arr = [1, 15, 10]
k = 6
print("Minimum difference:", get_minimized_difference(arr, k))
            

Output:

Minimum difference: 5