Geeksforgeeks: Minimize the Heights II

 Minimize the Heights II

Difficulty: Medium

Given an array arr[] denoting heights of N towers and a positive integer K.

For each tower, you must perform exactly one of the following operations exactly once.

• Increase the height of the tower by K
• Decrease the height of the tower by K

Find out the minimum possible difference between the height of the shortest and tallest towers after you have modified each tower.

You can find a slight modification of the problem here.
Note: It is compulsory to increase or decrease the height by K for each tower. After the operation, the resultant array should not contain any negative integers.

Examples :

Input: k = 2, arr[] = {1, 5, 8, 10}
Output: 5
Explanation: The array can be modified as {1+k, 5-k, 8-k, 10-k} = {3, 3, 6, 8}.The difference between the largest and the smallest is 8-3 = 5.

Input: k = 3, arr[] = {3, 9, 12, 16, 20}
Output: 11
Explanation: The array can be modified as {3+k, 9+k, 12-k, 16-k, 20-k} -> {6, 12, 9, 13, 17}.The difference between the largest and the smallest is 17-6 = 11. 

Constraints
1 ≤ k ≤ 107
1 ≤ n ≤ 105
1 ≤ arr[i] ≤ 107

 Here's the problem along with multiple approaches to solve it. Let's walk through each approach for finding the minimum possible difference between the height of the shortest and tallest towers after modifying their heights.

Problem:

Given an array arr[] denoting the heights of N towers and a positive integer K. For each tower, you must either:

• Increase its height by K, or
• Decrease its height by K.

You need to find out the minimum possible difference between the height of the shortest and tallest towers after performing the modification on each tower.

Approaches:

---

Approach 1: Greedy Solution (Sorting + Greedy Adjustment)

1. Sort the Array: Sorting helps because the smallest and largest towers influence the difference. Once sorted, we only need to manipulate the extremes of the array to minimize the difference.
2. Modify the Heights: For each tower, either increase or decrease its height by K and calculate the new difference.
3. Two Possible Configurations:
   • Modify the smallest tower by adding K and the largest tower by subtracting K.
   • Modify the smallest tower by subtracting K and the largest tower by adding K.
4. Calculate the Difference: After modification, compute the new height difference and track the minimum difference.

Code for Approach 1:

using System;

public class Solution {
    public int MinDifference(int[] arr, int k) {
        // Step 1: Sort the array
        Array.Sort(arr);

        // If there is only one tower, no operation can reduce the difference
        if (arr.Length == 1) return 0;

        int n = arr.Length;
        int initialDifference = arr[n - 1] - arr[0];  // Initial difference without any operation

        // Step 2: Start considering the possibilities
        int minDifference = initialDifference;

        for (int i = 0; i < n - 1; i++) {
            int small = Math.Min(arr[0] + k, arr[i + 1] - k);  // Modify the smallest tower or next smallest
            int large = Math.Max(arr[i] + k, arr[n - 1] - k);  // Modify the largest tower or next largest

            // Update the minimum possible difference
            minDifference = Math.Min(minDifference, large - small);
        }

        return minDifference;
    }
}

class Program {
    static void Main(string[] args) {
        Solution solution = new Solution();
        
        int[] arr1 = { 1, 5, 8, 10 };
        int k1 = 2;
        Console.WriteLine(solution.MinDifference(arr1, k1));  // Output: 5

        int[] arr2 = { 3, 9, 12, 16, 20 };
        int k2 = 3;
        Console.WriteLine(solution.MinDifference(arr2, k2));  // Output: 11
    }
}

Time Complexity:

• Sorting the array takes $O(n \log n)$.
• After sorting, the loop runs in $O(n)$, so the overall time complexity is $O(n \log n)$.

Space Complexity:

• The space complexity is $O(1)$ since no additional data structures are used apart from the input array.

---

Approach 2: Brute Force Solution (Exploring All Possibilities)

If you're looking for a simpler but inefficient solution:

1. Try All Possible Combinations: For each tower, try increasing or decreasing its height by K and calculate the difference between the tallest and shortest towers.
2. Find the Minimum Difference: After trying all combinations of modifying the towers, return the smallest difference found.

This approach works but is inefficient for larger arrays due to its exponential nature.

Code for Approach 2:

using System;

public class Solution {
    public int MinDifference(int[] arr, int k) {
        // If the array has only one element, the answer is 0 because no operation is needed
        if (arr.Length == 1) return 0;

        int n = arr.Length;
        int minDifference = int.MaxValue;

        // Explore all possibilities
        for (int i = 0; i < (1 << n); i++) {
            int[] temp = new int[n];
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) {
                    temp[j] = arr[j] + k;  // Increase height by K
                } else {
                    temp[j] = arr[j] - k;  // Decrease height by K
                }
            }

            // Find the difference between the largest and smallest heights
            int maxHeight = int.MinValue, minHeight = int.MaxValue;
            for (int j = 0; j < n; j++) {
                maxHeight = Math.Max(maxHeight, temp[j]);
                minHeight = Math.Min(minHeight, temp[j]);
            }

            minDifference = Math.Min(minDifference, maxHeight - minHeight);
        }

        return minDifference;
    }
}

class Program {
    static void Main(string[] args) {
        Solution solution = new Solution();
        
        int[] arr1 = { 1, 5, 8, 10 };
        int k1 = 2;
        Console.WriteLine(solution.MinDifference(arr1, k1));  // Output: 5

        int[] arr2 = { 3, 9, 12, 16, 20 };
        int k2 = 3;
        Console.WriteLine(solution.MinDifference(arr2, k2));  // Output: 11
    }
}

Time Complexity:

• The time complexity is $O(2^n)$, where $n$ is the size of the array. This is due to the need to try all possible combinations of increasing and decreasing each element.

Space Complexity:

• The space complexity is $O(n)$ because we're using an extra array to store the modified heights during the combinations.

---

Approach 3: Optimized Sliding Window (Dynamic Programming Variant)

While the above approaches focus on either sorting or brute force, a more dynamic programming or sliding window approach could optimize the process for large input sizes. You can use this technique to minimize the complexity of the operation but it's harder to achieve with this problem due to the constraints and operations required (increment and decrement).

For large $n$, the greedy approach mentioned in Approach 1 is generally the most efficient.