Minimize The Heights II

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. 

Expected Time Complexity: O(n*logn)
Expected Auxiliary Space: O(n)

Constraints
1 ≤ k ≤ 10⁷
1 ≤ n ≤ 10⁵
1 ≤ arr[i] ≤ 10⁷

Approach 01:

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int getMinDiff(vector<int>& array, int k) {
        int size = array.size();
        // Sort the array to easily calculate the min and max values
        sort(array.begin(), array.end());
        
        // Initialize the result with the maximum possible difference
        int minDifference = array[size - 1] - array[0];
        
        // Iterate through the array to find the minimum difference
        for (int i = 0; i < size; ++i) {
            // Calculate the potential maximum and minimum values within the range
            int maxElement = (i > 0) ? max(array[i - 1] + k, array[size - 1] - k) : array[size - 1] - k;
            int minElement = min(array[i] - k, array[0] + k);
            
            // Skip iterations where the minimum element is negative
            if (minElement < 0) {
                continue;
            }
            
            // Update the result with the minimum difference
            minDifference = min(minDifference, maxElement - minElement);
        }
        
        // Return the final result
        return minDifference;
    }
};

class Solution:
    def getMinDiff(self, array, k):
        size = len(array)
        # Sort the array to make it easier to find minimum and maximum values
        array.sort()
        
        # Initialize the result with the maximum possible difference
        minDifference = array[size - 1] - array[0]
        
        # Iterate through the array to find the minimum difference
        for i in range(size):
            # Calculate the potential maximum and minimum values within the range
            maxElement = max(array[i - 1] + k, array[size - 1] - k) if i > 0 else array[size - 1] - k
            minElement = min(array[i] - k, array[0] + k)
            
            # Skip iterations where the minimum element is negative
            if minElement < 0:
                continue
            
            # Update the result with the minimum difference
            minDifference = min(minDifference, maxElement - minElement)
        
        # Return the final result
        return minDifference

Time Complexity

• Sorting the Array:

  The algorithm begins by sorting the array, which takes \(O(n \log n)\), where \(n\) is the number of elements in the input array.

• Iterating through the Array:

  After sorting, the algorithm iterates through the array once to calculate the minimum difference, which takes \(O(n)\). Each operation inside the loop (calculating max, min, and comparing values) takes constant time \(O(1)\).

• Overall Time Complexity:

  The overall time complexity is \(O(n \log n)\) due to the sorting step, which dominates the iteration time.

Space Complexity

• Space for Sorting:

  The sorting step uses in-place sorting, which requires \(O(1)\) additional space.

• Space for Variables:

  Additional space is used for a few variables like minDifference, maxElement, and minElement, which all take constant space \(O(1)\).

• Overall Space Complexity:

  The overall space complexity is \(O(1)\), as the space used does not depend on the input size \(n\).