Minimise the maximum difference between heights [V.IMP]

Problem Statement

Given an array of heights of towers and a value K, you need to either increase or decrease the height of each tower by K (exactly once). After modifications, find the minimum possible difference between the heights of the longest and shortest towers.

Constraints: Heights cannot become negative after modification.

Example:

• Input: heights = [1, 5, 8, 10], K = 2
• Output: 5
• Explanation:
  • Modify to: [1+2, 5-2, 8-2, 10-2] = [3, 3, 6, 8]
  • Min = 3, Max = 8, Difference = 5

Approach 1: Brute Force (Try All Combinations)

Intuition

For each tower, we have two choices: add K or subtract K. Try all 2^n combinations and find the minimum difference.

Algorithm

1. Generate all possible combinations of +K and -K for each element
2. For each combination, calculate max - min
3. Return the minimum difference found

public class Solution {
    private int minDiff = Integer.MAX_VALUE;
    
    public int getMinDiff(int[] heights, int k) {
        solve(heights, k, 0, new ArrayList<>());
        return minDiff;
    }
    
    private void solve(int[] heights, int k, int idx, List<Integer> current) {
        if (idx == heights.length) {
            int maxH = Collections.max(current);
            int minH = Collections.min(current);
            if (minH >= 0) {
                minDiff = Math.min(minDiff, maxH - minH);
            }
            return;
        }
        
        // Add K
        current.add(heights[idx] + k);
        solve(heights, k, idx + 1, current);
        current.remove(current.size() - 1);
        
        // Subtract K
        current.add(heights[idx] - k);
        solve(heights, k, idx + 1, current);
        current.remove(current.size() - 1);
    }
}

Complexity Analysis

• Time Complexity: O(2^n × n) - 2^n combinations, O(n) to find min/max
• Space Complexity: O(n) - Recursion stack and current array

Approach 2: Greedy with Sorting (Optimal)

Intuition

After sorting, for the optimal solution:

• We should increase smaller elements (add K)
• We should decrease larger elements (subtract K)
• There exists a "breaking point" where we switch from adding to subtracting

After sorting, the minimum is either arr[0] + K or arr[i] - K for some i, and the maximum is either arr[n-1] - K or arr[i-1] + K.

Algorithm

1. Sort the array
2. Initial answer: arr[n-1] - arr[0] (no modification case baseline)
3. Consider smallest = arr[0] + K and largest = arr[n-1] - K
4. For each possible breaking point i (from 1 to n-1):
   • New min = min(smallest, arr[i] - K)
   • New max = max(largest, arr[i-1] + K)
   • Update answer if this gives smaller difference

import java.util.Arrays;

public class Solution {
    public int getMinDiff(int[] arr, int k) {
        int n = arr.length;
        if (n == 1) return 0;
        
        Arrays.sort(arr);
        
        // Initial answer: difference without any smart modification
        int ans = arr[n - 1] - arr[0];
        
        // After adding K to smallest and subtracting K from largest
        int smallest = arr[0] + k;
        int largest = arr[n - 1] - k;
        
        // Ensure smallest <= largest for valid range
        if (smallest > largest) {
            int temp = smallest;
            smallest = largest;
            largest = temp;
        }
        
        // Try each possible breaking point
        for (int i = 1; i < n; i++) {
            int subtract = arr[i] - k;
            int add = arr[i - 1] + k;
            
            // Skip if subtracting K makes height negative
            if (subtract < 0) continue;
            
            int currentMin = Math.min(smallest, subtract);
            int currentMax = Math.max(largest, add);
            
            ans = Math.min(ans, currentMax - currentMin);
        }
        
        return ans;
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n log n) - Due to sorting
• Space Complexity: O(1) - Ignoring sort space

Visual Understanding

Key Takeaways

1. Sorting transforms this into a breaking point problem
2. The greedy insight: increase small values, decrease large values
3. After sorting, we only need to try n breaking points
4. Handle the constraint: heights cannot be negative
5. Initial answer (no smart modification) serves as a baseline
6. This problem tests understanding of optimization through partitioning
7. Similar technique applies to problems like "minimize max difference in pairs"