Greedy
Array
Description
You are given m
arrays
, where each array is sorted in ascending order .
You can pick up two integers from two different arrays (each array picks one) and calculate the distance. We define the distance between two integers a
and b
to be their absolute difference |a - b|
.
Return the maximum distance .
Example 1:
Input: arrays = [[1,2,3],[4,5],[1,2,3]]
Output: 4
Explanation: One way to reach the maximum distance 4 is to pick 1 in the first or third array and pick 5 in the second array.
Example 2:
Input: arrays = [[1],[1]]
Output: 0
Constraints:
m == arrays.length
2 <= m <= 105
1 <= arrays[i].length <= 500
-104 <= arrays[i][j] <= 104
arrays[i]
is sorted in ascending order .
There will be at most 105
integers in all the arrays.
Solutions
Solution 1
Python3 Java C++ Go TypeScript JavaScript
class Solution :
def maxDistance ( self , arrays : List [ List [ int ]]) -> int :
ans = 0
mi , mx = arrays [ 0 ][ 0 ], arrays [ 0 ][ - 1 ]
for arr in arrays [ 1 :]:
a , b = abs ( arr [ 0 ] - mx ), abs ( arr [ - 1 ] - mi )
ans = max ( ans , a , b )
mi = min ( mi , arr [ 0 ])
mx = max ( mx , arr [ - 1 ])
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution {
public int maxDistance ( List < List < Integer >> arrays ) {
int ans = 0 ;
int mi = arrays . get ( 0 ). get ( 0 );
int mx = arrays . get ( 0 ). get ( arrays . get ( 0 ). size () - 1 );
for ( int i = 1 ; i < arrays . size (); ++ i ) {
var arr = arrays . get ( i );
int a = Math . abs ( arr . get ( 0 ) - mx );
int b = Math . abs ( arr . get ( arr . size () - 1 ) - mi );
ans = Math . max ( ans , Math . max ( a , b ));
mi = Math . min ( mi , arr . get ( 0 ));
mx = Math . max ( mx , arr . get ( arr . size () - 1 ));
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 class Solution {
public :
int maxDistance ( vector < vector < int >>& arrays ) {
int ans = 0 ;
int mi = arrays [ 0 ][ 0 ], mx = arrays [ 0 ][ arrays [ 0 ]. size () - 1 ];
for ( int i = 1 ; i < arrays . size (); ++ i ) {
auto & arr = arrays [ i ];
int a = abs ( arr [ 0 ] - mx ), b = abs ( arr [ arr . size () - 1 ] - mi );
ans = max ({ ans , a , b });
mi = min ( mi , arr [ 0 ]);
mx = max ( mx , arr [ arr . size () - 1 ]);
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 func maxDistance ( arrays [][] int ) ( ans int ) {
mi , mx := arrays [ 0 ][ 0 ], arrays [ 0 ][ len ( arrays [ 0 ]) - 1 ]
for _ , arr := range arrays [ 1 :] {
a , b := abs ( arr [ 0 ] - mx ), abs ( arr [ len ( arr ) - 1 ] - mi )
ans = max ( ans , max ( a , b ))
mi = min ( mi , arr [ 0 ])
mx = max ( mx , arr [ len ( arr ) - 1 ])
}
return ans
}
func abs ( x int ) int {
if x < 0 {
return - x
}
return x
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14 function maxDistance ( arrays : number [][]) : number {
const n = arrays . length ;
let res = 0 ;
let [ min , max ] = [ Number . POSITIVE_INFINITY , Number . NEGATIVE_INFINITY ];
for ( let i = 0 ; i < n ; i ++ ) {
const a = arrays [ i ];
res = Math . max ( Math . max ( a . at ( - 1 ) ! - min , max - a [ 0 ]), res );
min = Math . min ( min , a [ 0 ]);
max = Math . max ( max , a . at ( - 1 ) ! );
}
return res ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 /**
* @param {number[][]} arrays
* @return {number}
*/
var maxDistance = function ( arrays ) {
const n = arrays . length ;
let res = 0 ;
let [ min , max ] = [ Number . POSITIVE_INFINITY , Number . NEGATIVE_INFINITY ];
for ( let i = 0 ; i < n ; i ++ ) {
const a = arrays [ i ];
res = Math . max ( Math . max ( a . at ( - 1 ) - min , max - a [ 0 ]), res );
min = Math . min ( min , a [ 0 ]);
max = Math . max ( max , a . at ( - 1 ));
}
return res ;
};
Solution 2: One-line solution
TypeScript JavaScript
const maxDistance = ( arrays : number [][]) : number =>
arrays . reduce (
([ res , min , max ], a ) => [
Math . max ( Math . max ( a . at ( - 1 ) ! - min , max - a [ 0 ]), res ),
Math . min ( min , a [ 0 ]),
Math . max ( max , a . at ( - 1 ) ! ),
],
[ 0 , Number . POSITIVE_INFINITY , Number . NEGATIVE_INFINITY ],
)[ 0 ];
1
2
3
4
5
6
7
8
9
10
11
12
13 /**
* @param {number[][]} arrays
* @return {number}
*/
var maxDistance = arrays =>
arrays . reduce (
([ res , min , max ], a ) => [
Math . max ( Math . max ( a . at ( - 1 ) - min , max - a [ 0 ]), res ),
Math . min ( min , a [ 0 ]),
Math . max ( max , a . at ( - 1 )),
],
[ 0 , Number . POSITIVE_INFINITY , Number . NEGATIVE_INFINITY ],
)[ 0 ];