## DEV Community is a community of 642,931 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# 📍Minimize the maximum difference between heights📍

Kaiwalya Koparkar
Front-end Developer @Codemugg|🌐 Open Source Enthusiast | 💻 Full Stack Developer | 📎Blogger 📜| Competitive Programmer | Man who Dreams In Code 💻

Question :

Given an array arr[] denoting heights of N towers and a positive integer K, you have to modify the height of each tower either by increasing or decreasing them by K only once. After modifying, height should be a non-negative integer. Find out what could be the possible minimum difference of the height of shortest and longest towers after you have modified each tower.

Example 1:

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

Logic:

1. Naive Approach O(n logn):
• The idea is to sort all elements increasing order. And for all elements check if subtract(element-k) and add(element+k) makes any changes or not.
• Below is the implementation of the above approach:
• Sort the given array
• after sorting declare 3 variables namely
• ans = last element - first element
• small = first element + k
• big = last element - k
• place pointer on second element and subtrack = arr [ i ] - k and then add = arr [ i ] + k
• if add < big do nothing
• if subtrack > small do nothing
• at last return min ( ans, big-small)
import java.util.*;

public class Solution{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int k = sc.nextInt();
int n = sc.nextInt();
int arr[] = new int[n];

for(int i = 0; i < arr.length; i++){
arr[i] = sc.nextInt();
}

if (n == 1)
return;

// Sort all elements
Arrays.sort(arr);

// Initialize result
int ans = arr[n-1] - arr[0];

// Handle corner elements
int small = arr[0] + k;
int big = arr[n-1] - k;
int temp = 0;

if (small > big)
{
temp = small;
small = big;
big = temp;
}

// Traverse middle elements
for (int i = 1; i < n-1; i ++)
{
int subtract = arr[i] - k;
int add = arr[i] + k;

// If both subtraction and addition
// do not change diff
if (subtract >= small || add <= big)
continue;

// Either subtraction causes a smaller
// number or addition causes a greater
// number. Update small or big using
// greedy approach (If big - subtract
// causes smaller diff, update small
// Else update big)
if (big - subtract <= add - small)
small = subtract;
else