Greedy
Array
Hash Table
Sorting
Description
Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize
, and consists of groupSize
consecutive cards.
Given an integer array hand
where hand[i]
is the value written on the ith
card and an integer groupSize
, return true
if she can rearrange the cards, or false
otherwise.
Example 1:
Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]
Example 2:
Input: hand = [1,2,3,4,5], groupSize = 4
Output: false
Explanation: Alice's hand can not be rearranged into groups of 4.
Constraints:
1 <= hand.length <= 104
0 <= hand[i] <= 109
1 <= groupSize <= hand.length
Note: This question is the same as 1296: https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/
Solutions
Solution 1
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12 class Solution :
def isNStraightHand ( self , hand : List [ int ], groupSize : int ) -> bool :
cnt = Counter ( hand )
for v in sorted ( hand ):
if cnt [ v ]:
for x in range ( v , v + groupSize ):
if cnt [ x ] == 0 :
return False
cnt [ x ] -= 1
if cnt [ x ] == 0 :
cnt . pop ( x )
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 class Solution {
public boolean isNStraightHand ( int [] hand , int groupSize ) {
Map < Integer , Integer > cnt = new HashMap <> ();
for ( int v : hand ) {
cnt . put ( v , cnt . getOrDefault ( v , 0 ) + 1 );
}
Arrays . sort ( hand );
for ( int v : hand ) {
if ( cnt . containsKey ( v )) {
for ( int x = v ; x < v + groupSize ; ++ x ) {
if ( ! cnt . containsKey ( x )) {
return false ;
}
cnt . put ( x , cnt . get ( x ) - 1 );
if ( cnt . get ( x ) == 0 ) {
cnt . remove ( x );
}
}
}
}
return true ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 class Solution {
public :
bool isNStraightHand ( vector < int >& hand , int groupSize ) {
unordered_map < int , int > cnt ;
for ( int & v : hand ) ++ cnt [ v ];
sort ( hand . begin (), hand . end ());
for ( int & v : hand ) {
if ( cnt . count ( v )) {
for ( int x = v ; x < v + groupSize ; ++ x ) {
if ( ! cnt . count ( x )) {
return false ;
}
if ( -- cnt [ x ] == 0 ) {
cnt . erase ( x );
}
}
}
}
return true ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 func isNStraightHand ( hand [] int , groupSize int ) bool {
cnt := map [ int ] int {}
for _ , v := range hand {
cnt [ v ] ++
}
sort . Ints ( hand )
for _ , v := range hand {
if _ , ok := cnt [ v ]; ok {
for x := v ; x < v + groupSize ; x ++ {
if _ , ok := cnt [ x ]; ! ok {
return false
}
cnt [ x ] --
if cnt [ x ] == 0 {
delete ( cnt , x )
}
}
}
}
return true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 function isNStraightHand ( hand : number [], groupSize : number ) {
const cnt : Record < number , number > = {};
for ( const i of hand ) {
cnt [ i ] = ( cnt [ i ] ?? 0 ) + 1 ;
}
const keys = Object . keys ( cnt ). map ( Number );
for ( const i of keys ) {
while ( cnt [ i ]) {
for ( let j = i ; j < groupSize + i ; j ++ ) {
if ( ! cnt [ j ]) {
return false ;
}
cnt [ j ] -- ;
}
}
}
return true ;
}
Solution 2
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 from sortedcontainers import SortedDict
class Solution :
def isNStraightHand ( self , hand : List [ int ], groupSize : int ) -> bool :
if len ( hand ) % groupSize != 0 :
return False
sd = SortedDict ()
for h in hand :
if h in sd :
sd [ h ] += 1
else :
sd [ h ] = 1
while sd :
v = sd . peekitem ( 0 )[ 0 ]
for i in range ( v , v + groupSize ):
if i not in sd :
return False
if sd [ i ] == 1 :
sd . pop ( i )
else :
sd [ i ] -= 1
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 class Solution {
public boolean isNStraightHand ( int [] hand , int groupSize ) {
if ( hand . length % groupSize != 0 ) {
return false ;
}
TreeMap < Integer , Integer > tm = new TreeMap <> ();
for ( int h : hand ) {
tm . put ( h , tm . getOrDefault ( h , 0 ) + 1 );
}
while ( ! tm . isEmpty ()) {
int v = tm . firstKey ();
for ( int i = v ; i < v + groupSize ; ++ i ) {
if ( ! tm . containsKey ( i )) {
return false ;
}
if ( tm . get ( i ) == 1 ) {
tm . remove ( i );
} else {
tm . put ( i , tm . get ( i ) - 1 );
}
}
}
return true ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 class Solution {
public :
bool isNStraightHand ( vector < int >& hand , int groupSize ) {
if ( hand . size () % groupSize != 0 ) return false ;
map < int , int > mp ;
for ( int & h : hand ) mp [ h ] += 1 ;
while ( ! mp . empty ()) {
int v = mp . begin () -> first ;
for ( int i = v ; i < v + groupSize ; ++ i ) {
if ( ! mp . count ( i )) return false ;
if ( mp [ i ] == 1 )
mp . erase ( i );
else
mp [ i ] -= 1 ;
}
}
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 func isNStraightHand ( hand [] int , groupSize int ) bool {
if len ( hand ) % groupSize != 0 {
return false
}
m := treemap . NewWithIntComparator ()
for _ , h := range hand {
if v , ok := m . Get ( h ); ok {
m . Put ( h , v .( int ) + 1 )
} else {
m . Put ( h , 1 )
}
}
for ! m . Empty () {
v , _ := m . Min ()
for i := v .( int ); i < v .( int ) + groupSize ; i ++ {
if _ , ok := m . Get ( i ); ! ok {
return false
}
if v , _ := m . Get ( i ); v .( int ) == 1 {
m . Remove ( i )
} else {
m . Put ( i , v .( int ) - 1 )
}
}
}
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 function isNStraightHand ( hand : number [], groupSize : number ) : boolean {
const n = hand . length ;
if ( n % groupSize ) {
return false ;
}
const groups : number [][] = Array . from ({ length : n / groupSize }, () => []);
hand . sort (( a , b ) => a - b );
for ( let i = 0 ; i < n ; i ++ ) {
let isPushed = false ;
for ( const g of groups ) {
if ( g . length === groupSize || ( g . length && hand [ i ] - g . at ( - 1 ) ! !== 1 )) {
continue ;
}
g . push ( hand [ i ]);
isPushed = true ;
break ;
}
if ( ! isPushed ) {
return false ;
}
}
return true ;
}