Maximum Distance in Arrays - Leetcode 624 - Python

[@satyamjha68]

Solved it! And glad to inform you that I got an internship offer from google for next summer. Thank you so much for all great Leetcode solution explanations! You are a GOAT and this channel is great!!

[@sayanbiswas2116]

Congo Mate

[@vedanthaldia]

Hey Satyam! Congratulations, I am a junior at BITS Pilani and also giving my tests for SI season, would you mind giving any of your socials so that we can connect ?

[@satyamjha68]

@@vedanthaldia Linkedin: www.linkedin.com/in/satyam1942/

[@gamingsoumya3669]

How you have prepared???

[@GliderOne-uo2jy]

I'm glad to see ur story. I hope I can like you guys

[@33galactus]

That's a very ingenious solution, Navdeep. When I first solved it, I used a slightly different approach. To ensure that the minimum and maximum values belong to two different arrays, I tracked the top two maximum values and the top two minimum values, along with their array indices. I then calculated the maximum distance (maxval - minval) by comparing index values to ensure that the maximum and minimum values were from different arrays. However, your approach is much more elegant and simpler. Thank you.

[@BCS-IshtiyakAhmadKhan]

What about if top 2 max and top 2 min are from same array for example [1,2,17,18] ,[3,4] ,[5,6] etc .

[@33galactus]

@@BCS-IshtiyakAhmadKhan What I meant was to choose only one max and one min from each array but keep track of top two max and top two mins of overall input. Here in this example, top two max would be 18 & 6. And top two mins would be 1 & 3. If we don't maintain top two, we'll end up having max distance to be (18-1) which is wrong as they belong to same array. But since have top two max and mins, we can ensure that max distance does not belong to the same array. Hope it's clear now.

[@deadlyecho]

Me too, I did exactly the same 😂

[@michaelroditis1952]

​@@BCS-IshtiyakAhmadKhan we would take the minimum from one array and maximum from second array. If one array contained both max and min that doesn't mean that we discard both the max and the min from that array, we would only discard one of them

[@goldenx2417]

​​@@33galactuseven I did the same but my code passed only 120 cases still some.cases did not.pass can you share your code

[@EagleEye.2006]

This was a very big destiny for me....just now I was solving this question and I had one doubt in this question and I came to youtube and saw my subscription panel and saw that you have uploaded this question 3 min ago.... beautiful smile came❤😄

[@ap2s2000]

Tell me you're Indian without telling me you're Indian

[@EagleEye.2006]

@@ap2s2000 kal ana parso batata hoo!!

[@EagleEye.2006]

@@ap2s2000 kal ana parso batata hoo!!

[@_DashingAdi_]

@@ap2s2000 fr

[@GermainHirwa]

Hi Navdeep. Thank you for the solution. However, this approach fails for the last 4 test cases. just made a slight modification using the range for it to work for other test cases. This solves the issue where the first array might contain the minimum and the maximum numbers in the entire arrays. class Solution(object): def maxDistance(self, arrays): """ :type arrays: List[List[int]] :rtype: int """ curMin, curMax = arrays[0][0], arrays[0][-1] res = 0 for i in range(1, len(arrays)): # Start from the second array res = max( res, max(curMax - arrays[i][0], arrays[i][-1] - curMin) ) curMin = min(curMin, arrays[i][0]) curMax = max(curMax, arrays[i][-1]) return res

[@hoyinli7462]

ur solution is very clean!

[@anirudhkiran7640]

what if the min and max we set initially is in fact the min and max of the entire set of arrays? It won't get updated as we iterate through the rest causing the min and max to be in the same array. Wouldn't that violate the condition in the question?

[@nuggs_]

that is not exactly what the question is asking. The differences must be between two different arrays. So as you said, let the min and max of the first array be the global max and global mins. Let min(i) be any local min for remaining arrays. Let max(i) be any local max for all other arrays. Then some globalMax - min(i) or max(i) - globalMin will become our max distance. Does this make sense ? to go back to your last question: it is violating the condition in the question in that it is not a valid candidate for the max distance

[@stoppls1709]

that's what im confused about, what if another array had both the minimum and maximum, wouldnt both then be from the same array??

[@stoppls1709]

still dont completely get it, but the condition is not being violated because when we calculate res, we are looking at the current array and checking distance with min and max found so far, even if both cur_min, cur_max were in the same array, we would not compare the two together, instead we look at the next array's min and max to check if distance is bigger or not res = max(res, arr[-1] - cur_min, cur_max - arr[0]) you can see we arent doing res = max(res, cur_max - cur_min)

[@nuggs_]

@@stoppls1709 curr_min and curr_max are updated after checking for a max distance

[@nuggs_]

​@@stoppls1709 what condition are you referring to. the condition i read was "two values from two different arrays"

[@tranminhquang4541]

Another way to do this but it takes two passes . First pass , we find smallest and second smallest number of all arrays. Second pass, we take the max of each array and subtract it by the smallest number of all arrays if the smallest of the current array is not the smallest of all arrays . If smallest of current array happens to be smallest of all arrays , subtract max of cur array by second smallest of all array .

[@lucasdellatorre3737]

yeah, that was the first solution that came in my mind

[@OhImNinja]

was told this week i cleared google onsites and basically only used your content to prep, thanks for making these videos

[@salahmo5692]

Stop lying 🤥

[@OhImNinja]

@@salahmo5692 not lying lil bro keep studying

[@E1an9640]

Congrats brother. I am about to graduate and has been looking for jobs for quite some time ,but I am unable to get an interview atleast .Any suggestions/advices ?

[@kuvonchbeknormakhmatov]

Amazing solution, thanks

[@oldmajor5240]

I thought about the problem a little bit differently. Either the min and the max values are in different arrays, then we can just take the max - the min as the result, or otherwise it might be the max - second_min or second_max - min. So quickselect for the two smallest mins and two largest maxs will do. Time and Space complexity also turns out to be O(N) and O(1). def maxDistance(arrays: List[List[int]]) -> int: mins=nsmallest(2,((a[0],i) for i,a in enumerate(arrays))) maxs=nlargest(2,((a[-1],i) for i,a in enumerate(arrays))) return max(b-a for (a,i) in mins for (b, j) in maxs if i!=j)

[@mohamed44324]

good video as always! just one thing to maybe change in future videos that could make it easier for people to understand. While you were explaining, you had an example but you never used the example to explain the solution. Doing dry runs with an example test case is much more effective than just explaining the problem conceptually. Thank you!

[@keyboardbasher5769]

instead of ```for i in range (1, len(arrays)): ``` you could have done ```for arr in arrays[1:]: ```

[@varunallagh7462]

This Q is for premium users I have a good streak of 260 days but due to this question it will break and I don't have enough points to redeem 30 days premium. so is there any way I would be able to save my streak ?

[@chrischika7026]

you can solve it now

[@michaelroditis1952]

I don't have premium but was able to solve it

[@varunallagh7462]

@@michaelroditis1952 yeah now it is open, earlier it was asking for premium

[@deepakjain4481]

wasn't it easy

[@hasferrr]

why i can't come up with this solution, i did recursion memoization for this problem😭

[@ps_v.2.3.20]

Hey Neetcode, Are these questions being added in Neetcode All(580)?

[@shahzodshafizod]

What if we find the max and min in all arrays and return their subtraction at the end? Why are we calculating res in every step?

[@shahzodshafizod]

I got it. Because that min and max can be in the same array as in this example: [[1,4],[0,5]].

[@sirojiddinSoftwareEngineer]

I solved like you. Thank you a lot

[@prathikboppudi6569]

Let’s go great explaination

[@arnobdas6365]

what if curMin and curMax are updating from same sub array?

[@surendhar.k5172]

same doubt

[@arnobdas6365]

​@@surendhar.k5172 If these are updating from same sub array, but in every calculation it's like highest - array[0] or array[n-1] - lowest. It's clear that though curMin and curMax are updating from same sub array, but we use only once like curMin or curMax for which we get the maxDistance. We are not using curMin and curMax at the same time.

[@jamestwosheep]

Damn... I thought I managed to get a pretty good result by making 2 passes, but your solution is so much more concise that now I'm a little embarassed. 😅

[@aanishas1925]

0:18 yeah 😂

[@olzhasilyassov6794]

Please, explain me, how the code works with the test case: ((2,4),(0,5)). Why the written algorithm works correctly with this kind of the test case. I don't get it?!? 😅

[@gurumoorthysivakolunthu9878]

Hi Sorry couldn't get the logic... How min and max from different arrays logic works here - Ex - [ [ 1 , 20 ] , [ 5 , 6 ] ] -- in this case the min and max will be from same array, right... Please help me in this... Thank you....

[@qulinxao]

class Solution: def maxDistance(self, a: List[List[int]],o=0) -> int: l,*_,r=a.pop()*2 for x,y in ((v[0],v[-1])for v in a): o,l,r=max(o,abs(y-l),abs(r-x)),min(l,x),max(r,y) return o

[@jaanvirathore1850]

neetcode bro i have one question for you i want to see the first approach came in your mind... Question:- Two players are playing a game with a starting number of tokens. Player names are Mayur(P1) and Divyanshu(P2). Mayur always plays first, and the two players move in alternating turns. The game’s rules are as follows: In a single move, a player can remove either 2,3 or5 tokens from the game board. If a player is unable to make a move, that player loses the game. Given the starting number of tokens, find and print the name of the winner. Mayur is named First and Divyanshu is named Second. Each player plays optimally, meaning they will not make a move that causes them to lose the game if a winning move exists. For example, if n=4, Mayur can make the following moves: Mayur removes 2 tokens leaving 2. Divyanshu will then remove 2 tokens and win. Mayur removes 3 tokens leaving 1. Divyanshu cannot move and loses. Mayur would make the second play and win the game. Input Format The first line contains an integer t, the number of test cases. Each of the next t lines contains an integer n, the number of tokens in a test case. Output Format On a new line for each test case, print First if the first player is the winner. Otherwise print Second. Sample Input:- 8 1 2 3 4 5 6 7 10 Sample Output:- Second First First First First First Second First

[@takeuchi5760]

This sounds like a codeforces question

[@jaanvirathore1850]

@@takeuchi5760 this is asked in Accenture exam

[@michaelliu5770]

First!

[@kevinronald7171]

Second 🥈

[@laveshbhandari9719]

Third 🥉

[@NishantSingh-dy1xt]

third 🥉

[@sahilverma_dev]

I am doing leetcode daily I am here after my getting Time Limit Exceeded for my approach 🥲🥲