Minimize Maximum of Array - (META) | Leetcode-2439 | Explanation ➕ Live Coding 🧑🏻‍💻👩🏻‍💻

This is the 14th Video on our Binary Search Playlist.
In this video we will try to solve a very good and tricky problem on Binary Search "Minimize Maximum of Array" (Leetcode - 2439)

We will do live coding after explanation and see if we are able to pass all the test cases.

Problem Name : Minimize Maximum of Array
Company Tags : META

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish

[ajit]

Great !!! Was not getting intuition behind the use of binary search.

[satyasanjay]

Excellent explanation. It was a tricky problem. I have observed that in these types of problems figuring out the operation done on the array. If you can figure out the brute force approach then you can easily solve it using binary search.

*You can also take the left value as nums[0], because max of nums can not become less than nums[0]*
*So, the range will be [nums[0], max(nums)]*

Java Code:
class Solution {
boolean maxPossible(int[] nums, int max){
int n = nums.length;
long[] arr = new long[n];
for(int i = 0; i < n; i++){
arr[i] = nums[i];
}

for(int i = 0; i < n-1; i++){
if(arr[i] > max){
return false;
}
long buffer = max - arr[i];
arr[i] += buffer;
arr[i+1] -= buffer;
}

if(arr[n-1] > max){
return false;
}

return true;

}

public int minimizeArrayValue(int[] nums) {
int l = nums[0];
int r = Integer.MIN_VALUE;

for(int num: nums){
r = Math.max(r, num);
}

int ans = 0;
while(l <= r){
int mid = l + (r-l)/2;

if(maxPossible(nums, mid)){
ans = mid;
r = mid-1;
}
else{
l = mid+1;
}
}

return ans;
}
}

[anshumantripathy]

The maxL can be taken as nums[0] instead of 1 as nums[0] as it the lowest value of result, as already explained in the video. So the binary search will be between nums[0] and maximum value of nums[ ]. It will make the TC a bit better.
Thank you for your amazing explanation.

[_shashanks]

Please do vedios for leetcode contest solutions

[dayashankarlakhotia]

Good explanation. 2nd approach code write. Understood code with dryrun

[iamnoob]

Brilliant , I knew the intution behind BS, But was not sure how to detect/logic if that max chosen can be answer or not for each mid.

[HealthyOm]

we learn from u importance of dry run ... which was get frustations also but... its very important we see it in this vedio .... love u bhaiya ur hard works

[dayashankarlakhotia]

Class solution {
Public int minimize Array Value (int[]nums){
long ans=0 long sum=0;
for(int i=0;i<nums.length;++i){
Sum+=nums[i];
ans=MATH.MAX (ans, (sum+i/i+1));
}
return (int)ans;
}
};
Time complexity =(n)

[UmeshBisht-ikli]

Story explanation is next level❤
Thanku bhaiya

[AryanMishra-yhic]

please upload solutions of weekly contest as well. it will help us a lot.

[prajwalshaw]

Sir plz make a video on leetcode 1482 (minimum no.of days to make m bouquets)...which based on binary search on answer concept. I find it really difficult to understand this problem and you have a really unique way of making difficult concepts quite understandable. Thank you

[rajatrajgautam]

the solution clicked me at 17:31 .... coded it by myself then thanks

[JJ-tpdd]

Little change to avoid creating new array, space O(1)

class Solution {

private boolean isValid(int nums[], int mid, int n) {

if(nums[0] > mid) return false; // nums[0] ko kum toh kr skte ni

long prev = nums[0];

for(int i = 1; i < nums.length; i ++) {

long buffer = mid - prev;

if(nums[i] - buffer > mid) return false;

prev = nums[i] - buffer;
}

return true;
}

public int minimizeArrayValue(int[] nums) {

int n = nums.length;

int s = 0;
int e = 0;

int result = e;

for(int i=0; i<n; i++) {
e = Math.max(nums[i], e);
}

while(s <= e) {

int mid = s + (e-s)/2;

if(isValid(nums, mid, n)) {

result = mid;

e = mid-1;

}

else {

s = mid + 1;

}

}

return result;
}
}

[alphadrones]

if we use greedy, we can do it in O(n) but the binary seach intuition was awesome....

[study-ydes]

It was actually a tricky Question!! <3 thanks man

[JJ-tpdd]

Java implementation:

class Solution {

private boolean isValid(int nums[], int mid, int n) {

long[] arr =

for(int i=0; i<n-1; i++) {

if(arr[i] > mid) {

return false;
}

long buffer = mid - arr[i];

arr[i+1] = arr[i+1] - buffer;

}

return arr[n-1] <= mid;

}

public int minimizeArrayValue(int[] nums) {

int n = nums.length;

int s = 0;
int e = 0;

int result = e;

for(int i=0; i<n; i++) {
e = Math.max(nums[i], e);
}

while(s <= e) {

int mid = s + (e-s)/2;

if(isValid(nums, mid, n)) {

result = mid;

e = mid-1;

}

else {

s = mid + 1;

}

}

return result;
}
}

[harsh.jain]

Java solution : O(1) space complexity

class Solution {
boolean isMinMax(int[] nums, int midMax){

int n = nums.length;
long lastVal = nums[0];
long buffer = 0;

for(int i= 1; i<n; i++){
buffer = midMax - lastVal;
if((nums[i] - buffer) > midMax){
return false;
}
lastVal = nums[i]-buffer;
}
return true;
}

public int minimizeArrayValue(int[] nums) {
int n = nums.length;

int s = nums[0]; // minMax can't be less than first elem as it can't be reduced
int e = // max elem of nums arr
int possibleAns = nums[0];

while(s <= e){
int mid = s+(e-s)/2;

if( isMinMax(nums, mid) ){
possibleAns = mid;
e = mid-1;
}
else{
s = mid+1;
}
}
return possibleAns;
}
}

[manauwarzulfekaransari]

Here is the javascript code of above problem

var isValid = function(nums, expectedMax){
let arr = [...nums];
for(let i = 0 ; i < arr.length-1 ; i++){
if(arr[i] > expectedMax){
return false;
}else{
let buffer = Math.abs(arr[i]-expectedMax);
arr[i+1] -= buffer;
}
}
return arr[arr.length-1] <= expectedMax;
}
var minimizeArrayValue = function(nums) {

let ans = 0;
let l = 0;
let r = Math.max(...nums);

while(l <= r){
let m = Math.floor(l + (r-l)/2);
if(isValid(nums, m)){
ans = m;
r = m - 1;
}else{
l = m + 1;
}
}
return ans;
};

[shauncrasta]

My main question is why do we need to get the 0th element to maximum? Why not change only the elements that are > x. x being the desired max. What is the requirement to do it. Can you please discuss the proof for it bhaiya?

[prashantb]

What if nums[i+1] goes in negative when subtracted with buffer wont that be a problem ? It is given in question nums[i]>0