Greedy
Array
Hash Table
Sorting
Description
Given an integer array of even length arr
, return true
if it is possible to reorder arr
such that arr[2 * i + 1] = 2 * arr[2 * i]
for every 0 <= i < len(arr) / 2
, or false
otherwise .
Example 1:
Input: arr = [3,1,3,6]
Output: false
Example 2:
Input: arr = [2,1,2,6]
Output: false
Example 3:
Input: arr = [4,-2,2,-4]
Output: true
Explanation: We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].
Constraints:
2 <= arr.length <= 3 * 104
arr.length
is even.
-105 <= arr[i] <= 105
Solutions
Solution 1
Python3 Java C++ Go
class Solution :
def canReorderDoubled ( self , arr : List [ int ]) -> bool :
freq = Counter ( arr )
if freq [ 0 ] & 1 :
return False
for x in sorted ( freq , key = abs ):
if freq [ x << 1 ] < freq [ x ]:
return False
freq [ x << 1 ] -= freq [ x ]
return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution {
public boolean canReorderDoubled ( int [] arr ) {
Map < Integer , Integer > freq = new HashMap <> ();
for ( int v : arr ) {
freq . put ( v , freq . getOrDefault ( v , 0 ) + 1 );
}
if (( freq . getOrDefault ( 0 , 0 ) & 1 ) != 0 ) {
return false ;
}
List < Integer > keys = new ArrayList <> ( freq . keySet ());
keys . sort ( Comparator . comparingInt ( Math :: abs ));
for ( int k : keys ) {
if ( freq . getOrDefault ( k << 1 , 0 ) < freq . get ( k )) {
return false ;
}
freq . put ( k << 1 , freq . getOrDefault ( k << 1 , 0 ) - freq . get ( k ));
}
return true ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution {
public :
bool canReorderDoubled ( vector < int >& arr ) {
unordered_map < int , int > freq ;
for ( int & v : arr ) ++ freq [ v ];
if ( freq [ 0 ] & 1 ) return false ;
vector < int > keys ;
for ( auto & [ k , _ ] : freq ) keys . push_back ( k );
sort ( keys . begin (), keys . end (), []( int a , int b ) { return abs ( a ) < abs ( b ); });
for ( int & k : keys ) {
if ( freq [ k * 2 ] < freq [ k ]) return false ;
freq [ k * 2 ] -= freq [ k ];
}
return true ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 func canReorderDoubled ( arr [] int ) bool {
freq := make ( map [ int ] int )
for _ , v := range arr {
freq [ v ] ++
}
if freq [ 0 ] % 2 != 0 {
return false
}
var keys [] int
for k := range freq {
keys = append ( keys , k )
}
sort . Slice ( keys , func ( i , j int ) bool {
return abs ( keys [ i ]) < abs ( keys [ j ])
})
for _ , k := range keys {
if freq [ k * 2 ] < freq [ k ] {
return false
}
freq [ k * 2 ] -= freq [ k ]
}
return true
}
func abs ( x int ) int {
if x < 0 {
return - x
}
return x
}
GitHub