Leetcode 846. Hand of Straights

Problem Explanation

Alice has a hand of cards that she wishes to rearrange into consecutive groups. Each group must contain exactly W cards and each card within the group must be consecutive (i.e., if card n is in the group, then cards n - 1, n - 2, ..., n - (W - 1) must also be in that group).

She can only do this if all cards can form groups of W cards. For example, if she has an hand of cards [1,2,3,4,5,6,7,8,9] and she wants to form groups of W=4 cards, then she can form two groups ( [1, 2, 3, 4] and [5, 6, 7, 8]). But, she is left with one card (9) which can't form a group of W cards.

We are required to return true if she can form groups of W cards and false otherwise.

Problem Approach

We take a greedy approach to break the cards into groups of size W. We first count the frequency of each card number using a map. Our aim is to exhaust each card rightly, such that we will be able to form groups of W cards. The solution starts by observing that our groups should necessarily start with the smallest card. Hence, for the smallest card start, we count the number of groups value that will start with start. For each group that will start with start, we use value cards from cards start,start + 1, ..., start + groupSize - 1 to form the group. If at all for any card, it's count goes negative, it suggests that we are trying to use more cards than what we actually have, which will hint at the fact that it is impossible to partition the cards into groups.

Solution : Python

1
2python
3class Solution:
4    def isNStraightHand(self, hand, W):
5        count = collections.Counter(hand)
6        
7        for start in sorted(hand):
8            if count[start] > 0:
9                for card in range(start, start + W):
10                    if count[card] < count[start]:
11                        return False
12                    count[card] -= count[start]
13        
14        return True

Solution : Java

1
2java
3class Solution {
4
5    public boolean isNStraightHand(int[] hand, int W) {
6        TreeMap<Integer, Integer> count = new TreeMap<>();
7        
8        for (int card: hand) {
9            if (!count.containsKey(card))
10                count.put(card, 1);
11            else
12                count.replace(card, count.get(card) + 1);
13        }
14
15        while (count.size() > 0) {
16            int first = count.firstKey();
17            for (int card = first; card < first + W; ++card) {
18                if (!count.containsKey(card)) return false;
19                int c = count.get(card);
20                if (c == 1) count.remove(card);
21                else count.replace(card, c - 1);
22            }
23        }
24
25        return true;
26    }
27}

Solution : JavaScript

1
2javascript
3var isNStraightHand = function(hand, W) {
4    const count = new Map([...Array(16)].map((_,i) => [i, 0]));
5    let min = Infinity, max = -Infinity;
6    for(let num of hand) {
7        count.set(num, count.get(num) + 1);
8        min = Math.min(min, num);
9        max = Math.max(max, num);
10    }
11
12    while(min <= max&& count.get(min) > 0) {
13        let start = min;
14        while(count.get(start) > 0) {
15            count.set(start, count.get(start) - 1);
16            start++;
17        }
18        while(count.get(min) === 0 && min <= max) {
19            min++;
20        }
21    }
22
23    return Array.from(count.values()).every(val => val === 0);
24};

Solution : C++

1
2C++
3class Solution {
4public:
5    bool isNStraightHand(vector<int>& hand, int W) {
6        map<int, int> count;
7        for (const int card: hand)
8            ++count[card];
9
10        for(const auto& c: count) {
11            int start = c.first, value = c.second;
12            if (value > 0) {
13                for (int i = start; i < start + W; ++i) {
14                    count[i] -= value;
15                    if (count[i] < 0)
16                        return false;
17                }
18            }
19        }
20
21        return true;
22    }
23};

Solution : C#

1
2CSharp
3public class Solution {
4    private static SortedDictionary<int, int> GetCount(int[] hand) {
5        SortedDictionary<int, int> count = new SortedDictionary<int, int>();
6
7        foreach(int card in hand) {
8            int value;
9            if(count.TryGetValue(card, out value)) {
10                count[card] = value + 1;
11            } else {
12                count.Add(card, 1);
13            }
14        }
15
16        return count;
17    }
18
19    public bool IsNStraightHand(int[] hand, int W) {
20        SortedDictionary<int, int> count = GetCount(hand);
21
22        while(count.Count > 0) {
23            int first = count.First().Key;
24            for(int i = 0; i < W; i++) {
25                int occurence;
26                if(!count.TryGetValue(first + i, out occurence))
27                    return false; 
28                
29                if(occurence == 1)
30                    count.Remove(first + i);
31                else
32                    count[first + i] = occurence - 1;
33            }
34        }
35
36        return true;
37    }
38}

Problem Analysis

The key to solving this problem lies in understanding the conditions under which the cards can be arranged into W consecutive groups. The idea is to arrange the cards into groups starting from the smallest card. Here is the crux of the algorithm:

  1. For each smallest ungrouped card, we check the W consecutive cards following it.
  2. If any of these cards are missing, Alice wouldn't be able to arrange these cards into a group of consecutive cards, hence return false.
  3. If the count of least ungrouped card is more than the count of the next bigger ungrouped card, we conclude that the deck has been partitioned incorrectly and Alice wouldn't be able to form groups, so we return false.
  4. If none of these invalid conditions are encountered, we continue the process for all cards in Alice's hand.

Solution : Python

This solution begins by counting the occurrence of each card using collections.Counter and stores it in the count dictionary. It then examines each card starting from the smallest.

For each card start, the algorithm attempts to form W consecutive groups using count[start] cards. If we end up trying to use more cards than what we currently have (indicates by count going negative), we return False. If all cards have been used such that it was possible to form W groups, we return True.

1
2python
3import collections
4
5def isNStraightHand(hand, W):
6    count = collections.Counter(hand)
7    
8    for start in sorted(hand):
9        if count[start] > 0:
10            for card in range(start, start + W):
11                if count[card] < count[start]:
12                    return False
13                count[card] -= count[start]
14    
15    return True

Test the solution in Python

We can test our function using the following code:

1
2python
3print(isNStraightHand([1,2,3,6,2,3,4,7,8],3)) # returns True
  • Alice can form [1,2,3],[2,3,4] and [6,7,8] groups of W consecutive cards
1
2python
3print(isNStraightHand([1,2,3,4,5,6],2)) # returns False
  • Alice cannot form 2 groups of W consecutive cards

Conclusion

This problem emphasizes the usage of greedy algorithm under the right constraints. There are multiple solutions presented across different programming languages such as Python, Java, JavaScript, C# and C++. These solutions follow the same algorithmic approach with slight syntax differences. The understanding and implementation of the greedy strategy is the key to solving this problem.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫