Day 9 - Minimize the Heights II.md

Difficulty	Source	Tags
Medium	160 Days of Problem Solving	Arrays Greedy

🚀 Day 9. Minimize the Heights II 🧠

The problem can be found at the following link: Problem Link

💡 Problem Description:

Given an array arr[] denoting the heights of N towers and a positive integer K, you are required to perform one of the following operations for each tower:

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

Your task is to find out the minimum possible difference between the height of the tallest and shortest towers after performing the operations on each tower.

Note:

• It is compulsory to either increase or decrease the height of the tower by K for each tower.
• After the operation, the resultant array should not contain any negative integers.

🔍 Example Walkthrough:

Input:
k = 2, arr[] = {1, 5, 8, 10}
Output:
5

Explanation:
After performing the operations, the modified heights will be {3, 3, 6, 8}. The difference between the largest and smallest heights is 8 - 3 = 5.

Input:
k = 3, arr[] = {3, 9, 12, 16, 20}
Output:
11

Explanation:
After performing the operations, the modified heights will be {6, 12, 9, 13, 17}. The difference between the largest and smallest heights is 17 - 6 = 11.

Constraints:

• 1 ≤ k ≤ 10^7
• 1 ≤ n ≤ 10^5
• 1 ≤ arr[i] ≤ 10^7

🎯 My Approach:

1. Greedy Approach:

   • Sort the array of heights.
   • The goal is to minimize the difference between the tallest and shortest towers after performing the operations.
   • For each tower, choose whether to increase or decrease the height in such a way that the difference is minimized.
   • Calculate the difference between the modified tallest and shortest tower.

2. Steps:

   • Sort the array of heights.
   • Iterate through the array and try both options (increase or decrease) for each tower.
   • Track the minimum possible difference between the maximum and minimum tower heights after modifying the heights.

🕒 Time and Auxiliary Space Complexity 📝

• Expected Time Complexity: O(n log n), where n is the size of the array. Sorting the array takes O(n log n), and the rest of the operations are linear.
• Expected Auxiliary Space Complexity: O(n), as we store the modified heights in an auxiliary space.

📝 Solution Code

Code (C++)

class Solution {
public:
    int getMinDiff(vector<int>& arr, int k) {
        int n = arr.size();
        vector<pair<int, int>> modifiedHeights;
        vector<int> frequency(n, 0);

        for (int i = 0; i < n; i++) {
            if (arr[i] - k >= 0) {
                modifiedHeights.emplace_back(arr[i] - k, i);
            }
            modifiedHeights.emplace_back(arr[i] + k, i);
        }

        sort(modifiedHeights.begin(), modifiedHeights.end());

        int left = 0, right = 0, covered = 0, minDifference = INT_MAX;

        while (right < modifiedHeights.size()) {
            if (frequency[modifiedHeights[right].second]++ == 0) {
                covered++;
            }

            while (covered == n) {
                minDifference = min(minDifference, modifiedHeights[right].first - modifiedHeights[left].first);

                if (--frequency[modifiedHeights[left].second] == 0) {
                    covered--;
                }
                left++;
            }
            right++;
        }

        return minDifference;
    }
};

Code (Java)

class Solution {
    public int getMinDiff(int[] arr, int k) {
        int n = arr.length;
        List<int[]> modifiedHeights = new ArrayList<>();
        int[] frequency = new int[n];

        for (int i = 0; i < n; i++) {
            if (arr[i] - k >= 0) {
                modifiedHeights.add(new int[]{arr[i] - k, i});
            }
            modifiedHeights.add(new int[]{arr[i] + k, i});
        }

        modifiedHeights.sort(Comparator.comparingInt(a -> a[0]));

        int left = 0, right = 0, covered = 0, minDifference = Integer.MAX_VALUE;

        while (right < modifiedHeights.size()) {
            if (frequency[modifiedHeights.get(right)[1]]++ == 0) {
                covered++;
            }

            while (covered == n) {
                minDifference = Math.min(minDifference, modifiedHeights.get(right)[0] - modifiedHeights.get(left)[0]);

                if (--frequency[modifiedHeights.get(left)[1]] == 0) {
                    covered--;
                }
                left++;
            }
            right++;
        }

        return minDifference;
    }
}

Code (Python)

class Solution:
    def getMinDiff(self, arr, k):
        n = len(arr)
        if n == 1: 
            return 0
        arr.sort()

        ans = arr[-1] - arr[0]

        for i in range(n - 1):
            high = max(arr[i] + k, arr[-1] - k)
            low = min(arr[0] + k, arr[i + 1] - k)
            if low < 0:
                continue

            ans = min(ans, high - low)

        return ans

🎯 Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count