This question was asked in InterviewBit Academy Enterance Test on 16 Feb.
Given an array of integer A of size N. Minimize the absolute difference between maximum and minimum element of the array.
You can perform two types of operations atmost B times in total to change the values in the array. Multiple operations can be performend on the same element.
Increment :A[i] \rightarrow A[i] + 1
Decrement :A[i] \rightarrow A[i] - 1
Return the minimum difference possible.
Constraints 1 \leq N \leq 10^{5} 1 \leq A[i] \leq 10^{6} 1 \leq B \leq 10^{9}
int i, j;
int n = A.size();
int dp[1000010] = {0};
int mi = INT_MAX;
int ma = INT_MIN;
for(i = 0; i < n; i++){
dp[A[i]]++;
if(A[i] < mi){
mi = A[i];
}
if(A[i] > ma){
ma = A[i];
}
}
i = mi;
j = ma;
int ans = j-i;
int freqMin = dp[i];
int freqMax = dp[j];
while(i < j){
if(B < min(freqMin, freqMax)){
break;
}
if(freqMin < freqMax){
B -= freqMin;
freqMin += dp[i+1];
i++;
}
else{
B -= freqMax;
freqMax += dp[j-1];
j--;
}
ans = j-i;
}
return ans;
We can solve this using HashMap without binary search also.
public static int minimizeDif(ArrayList<Integer> A, int B) {
int min = Integer.MAX_VALUE;
int max= Integer.MIN_VALUE;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
// find the min and max in the array
// Also hash the whole array to find the occurrences of all elements
for (int i=0; i<A.size(); i++) {
min = Math.min(min, A.get(i));
max = Math.max(max, A.get(i));
map.put(A.get(i), map.getOrDefault(A.get(i), 0)+1);
}
// terminating condition if B<=0 can't perform any more ops
while (B>0 && min<max) {
// if the occurrences of min < if the occurrences of max
// => increase min by 1
// else decrease max by 1
if (map.getOrDefault(min, 0) < map.getOrDefault(max, 0)) {
// check if the occurrences of min element in array is less than the number of available number ops
if (B < map.getOrDefault(min, 0))
break;
map.put( min+1, map.getOrDefault(min+1, 0) +
map.get(min) );
B-= map.get(min);
min = min + 1;
}
else {
//check if the occurrences of max element in array is less than the number of available number ops
if (B < map.getOrDefault(max, 0))
break;
map.put( max-1, map.getOrDefault(max-1, 0) +
map.get(max) );
B-= map.get(max);
max = max - 1;
}
}
return max - min;
}
TC => O(n) + O(range of min and max)
SC => O(n) + O(range of min and max)