Maximum Distance in Arrays - Leetcode 624 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
6:35 - Coding Explanation

leetcode 624

#neetcode #leetcode #python

[satyamjha]

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!!

[galactus]

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.

[EagleEye.]

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❤😄

[OhImNinja]

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

[tranminhquang]

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 .

[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

[keyboardbasher]

instead of
```for i in range (1, len(arrays)): ```

you could have done

```for arr in arrays[1:]: ```

[oldmajor]

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)

[mohamed]

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!

[anirudhkiran]

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?

[varunallagh]

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 ?

[ps_v...]

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

[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. 😅

[gurumoorthysivakolunthu]

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....

[olzhasilyassov]

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?!? 😅

[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?

[hasferrr]

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

[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

[arnobdas]

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

[jaanvirathore]

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