2347. Best Poker Hand

EasyArrayHash TableCounting
Leetcode Link

Problem Description

The problem involves simulating the evaluation of a poker hand with given ranks and suits of cards. You are provided with two arrays: one for the ranks of the cards (ranks) and one for the suits (suits). The task is to determine the best poker hand from the following options, ranked from best to worst: "Flush", "Three of a Kind", "Pair", and "High Card".

A "Flush" is when all five cards have the same suit. A "Three of a Kind" is when three of the cards have the same rank. A "Pair" is when two of the cards have the same rank. If none of these hands are possible, you have a "High Card", which is your hand's highest ranking card.

You need to identify which of these hands you can form with your cards and return a string that represents the best possible hand.

Intuition

The intuition behind approaching this solution is to categorize the poker hand hierarchies and check for the presence of each type starting from the best ranking hand to the worst.

  • The best hand we can have is a "Flush". Since a "Flush" requires all cards to be of the same suit, we can simply check if the suits array contains the same suit for every card. If this condition is met, we can return "Flush" right away without checking for other possibilities because "Flush" is the highest-ranked hand we're considering in this problem.

  • Next, we can look for "Three of a Kind". Counting the occurrence of each rank in the ranks array helps us to identify if there are any three cards of the same rank. If we find that any rank appears at least three times, we have "Three of a Kind".

  • If "Three of a Kind" doesn't exist, we move on to check for a "Pair". Similarly to the previous step, if we find that any rank appears exactly twice, we have a "Pair".

  • Lastly, if none of the above hands are formed, by default we have a "High Card". There's no need to identify which card it is, since "High Card" simply refers to the situation where none of the other hands are possible.

By checking for each type of hand in the order of their ranks and returning as soon as we find a match, we can efficiently determine the best possible poker hand.

Solution Approach

The implementation of the solution uses a few fundamental algorithms, data structures, and patterns:

  1. Set and Frequency Counting:

    • Flush Check: To identify a "Flush," we're looking for the uniqueness of suits. If all suits are the same, the set of suits would have a length of 1. However, instead of converting suits into a set, which has a time complexity of O(n), an optimized approach checking all(a == b for a, b in pairwise(suits)) is used. This uses the pairwise function from Python's itertools module to check if every adjacent pair of elements is the same. If they are all the same, it's a flush.
    • Frequency Counting: To identify "Three of a Kind" and "Pair", we can use counting to track the frequency of each rank. This is done with Counter from the collections module. The Counter object, cnt, maps each rank to the number of times it appears in the ranks list.
  2. Conditional Logic:

    • The checks are done in a particular order, from the best hand to the worst. This is done using a series of if statements.
    • First, the "Flush" is checked. If the "Flush" condition is met, the function immediately returns 'Flush', since we do not need to check for other hand types.
    • If the condition for "Flush" is not met, the frequency count (cnt) is used to check if there's any rank that appears at least 3 times for "Three of a Kind".
    • If there is no "Three of a Kind", the function then checks for "Pair" by looking for any rank that appears exactly twice in the cnt.
    • If neither of those hands are possible, the function returns 'High Card' by default as it's the lowest hand that can be made with any set of cards.

This approach uses efficient data structures to minimize the time complexity and leverages the power of the Python standard library for counting and pairwise comparison to simplify the logic.

The solution encapsulates each of these checks within a single class method bestHand, which takes two arguments: ranks and suits, corresponding to the ranks and suits of the cards in the poker hand.

1class Solution:
2    def bestHand(self, ranks: List[int], suits: List[str]) -> str:
3        # Check for Flush
4        if all(a == b for a, b in pairwise(suits)):
5            return 'Flush'
6          
7        cnt = Counter(ranks)
8      
9        # Check for Three of a Kind
10        if any(v >= 3 for v in cnt.values()):
11            return 'Three of a Kind'
12          
13        # Check for Pair
14        if any(v == 2 for v in cnt.values()):
15            return 'Pair'
16      
17        # If none of the above, return High Card
18        return 'High Card'

This code provides an efficient solution to the problem by methodically checking for each type of poker hand in decreasing order of rank and is an example of how understanding the domain (poker hands ranking) aids in crafting a clear and concise algorithm.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Example Walkthrough

Let's consider an example where you have the following hand of cards:

  • Ranks: [10, 7, 10, 4, 3]
  • Suits: ['H', 'D', 'H', 'S', 'H']

Let's walk through the solution approach step by step:

  1. Flush Check: We first check if there's a "Flush". We compare each suit with the next one by pairwise comparison:

    • 'H' == 'D'? No.
    • Since not all suits are the same, it's not a "Flush". We move on to the next check.
  2. Frequency Counting for "Three of a Kind" and "Pair":

    • Create a frequency count of the ranks using Counter:
      • Counter([10, 7, 10, 4, 3]) results in {10: 2, 7: 1, 4: 1, 3: 1}
    • Check for "Three of a Kind" by looking for any rank that appears three times:
      • Since no rank has a frequency of 3 or more, we do not have a "Three of a Kind".
    • Since there's no "Three of a Kind", we move on to check for a "Pair":
      • We find that the rank 10 appears twice (10: 2).
      • This confirms that we have a "Pair" for this hand.
  3. Final Hand Determination:

    • We do not proceed any further since we have already identified a "Pair", which takes precedence over "High Card".

Thus, according to our solution approach, the function bestHand would return 'Pair' as the best hand possible with the given cards.

Solution Implementation

1from typing import List
2from collections import Counter
3from itertools import pairwise
4
5class Solution:
6    def bestHand(self, ranks: List[int], suits: List[str]) -> str:
7        # Check if all suits are the same by comparing each pair of adjacent suits.
8        # If so, return 'Flush' since all cards have the same suit.
9        if all(suit1 == suit2 for suit1, suit2 in pairwise(suits)):
10            return 'Flush'
11      
12        # Use a Counter to count the occurrences of each rank.
13        rank_counter = Counter(ranks)
14      
15        # Check if there's any rank with at least three occurrences.
16        # If so, return 'Three of a Kind'.
17        if any(count >= 3 for count in rank_counter.values()):
18            return 'Three of a Kind'
19      
20        # Check for any rank with exactly two occurrences.
21        # If so, return 'Pair'.
22        if any(count == 2 for count in rank_counter.values()):
23            return 'Pair'
24      
25        # If none of the above conditions are met, return 'High Card'.
26        return 'High Card'
27
1class Solution {
2    // Method to determine the best hand from the given ranks and suits of cards
3    public String bestHand(int[] ranks, char[] suits) {
4        // Initially assume we have a flush (all suits are the same)
5        boolean isFlush = true;
6        // Check all card suits; if any are different, set isFlush to false
7        for (int i = 1; i < 5 && isFlush; ++i) {
8            if (suits[i] != suits[i - 1]) {
9                isFlush = false;
10            }
11        }
12      
13        // If all card suits are the same, we have a flush
14        if (isFlush) {
15            return "Flush";
16        }
17      
18        // Counter for the occurrences of each rank
19        int[] rankCount = new int[14];
20        // Flag to indicate if at least one pair has been found
21        boolean hasPair = false;
22      
23        // Iterate over all the ranks to count occurrences and identify pairs or three of a kind
24        for (int rank : ranks) {
25            rankCount[rank]++;
26            // If a rank count reaches 3, we have a three of a kind
27            if (rankCount[rank] == 3) {
28                return "Three of a Kind";
29            }
30            // If a rank count is exactly 2, note that we have a pair
31            if (rankCount[rank] == 2) {
32                hasPair = true;
33            }
34        }
35      
36        // Return the best hand based on whether we've found a pair or have only high card
37        return hasPair ? "Pair" : "High Card";
38    }
39}
40
1class Solution {
2public:
3    string bestHand(vector<int>& ranks, vector<char>& suits) {
4        // Check if all the suits are the same, which would mean a Flush.
5        bool isFlush = true;
6        for (int i = 1; i < 5 && isFlush; ++i) {
7            isFlush = suits[i] == suits[i - 1];
8        }
9        if (isFlush) {
10            return "Flush";
11        }
12
13        // Initialize an array to count occurrences of each rank.
14        int rankCounts[14] = {0};
15        bool hasPair = false; // Flag to check if there is at least one pair.
16      
17        // Count the occurrences of each rank and check for Three of a Kind or Pair.
18        for (int& rank : ranks) {
19            rankCounts[rank]++;
20          
21            // If a rank appears three times, it is Three of a Kind.
22            if (rankCounts[rank] == 3) {
23                return "Three of a Kind";
24            }
25          
26            // If a rank appears twice, we mark that we have found a pair.
27            hasPair = hasPair || rankCounts[rank] == 2;
28        }
29
30        // Return "Pair" if a pair was found, otherwise return "High Card".
31        return hasPair ? "Pair" : "High Card";
32    }
33};
34
1function bestHand(ranks: number[], suits: string[]): string {
2    // Check for a Flush: all suits are the same
3    if (suits.every(suit => suit === suits[0])) {
4        return 'Flush';
5    }
6
7    // Initialize a counter array to hold the frequency of each rank
8    const rankCounts = new Array(14).fill(0);
9    let hasPair = false; // Flag to check if a Pair has been found
10
11    // Loop through the ranks to count occurrences of each rank
12    for (const rank of ranks) {
13        rankCounts[rank]++;
14      
15        // If a rank count reaches 3, we have a 'Three of a Kind'
16        if (rankCounts[rank] === 3) {
17            return 'Three of a Kind';
18        }
19      
20        // Check if we have at least one pair
21        hasPair = hasPair || rankCounts[rank] === 2;
22    }
23
24    // If a pair was found, return 'Pair'
25    if (hasPair) {
26        return 'Pair';
27    }
28
29    // If none of the above hands are found, return 'High Card'
30    return 'High Card';
31}
32

Time and Space Complexity

The given Python function bestHand determines the best hand possible in a card game based on the suits and ranks of the cards provided. Here is an analysis of its complexity:

Time Complexity:

  1. all(a == b for a, b in pairwise(suits)): This checks if all elements in suits are the same. Assuming pairwise is an iterable that provides tuples of successive pairs from suits, this operation has a time complexity of O(n), where n is the number of suits.

  2. Counter(ranks): Counting the frequency of each rank has a time complexity of O(m), where m is the number of ranks.

  3. any(v >= 3 for v in cnt.values()): Iterating over the values of the counter to check for a 'Three of a Kind' has a worst-case time complexity of O(m).

  4. any(v == 2 for v in cnt.values()): Similarly, this check for a 'Pair' has a time complexity of O(m).

Since the number of cards in a hand is typically small and fixed (for example, 5 in many games), both n and m can be considered constants, and the time complexity can be simplified to O(1).

Space Complexity:

  1. Counter(ranks): The counter here creates a dictionary with a unique entry for each rank. The space complexity is O(m) since it stores as many entries as there are unique ranks.

  2. Temporal space needed to store the pairs in pairwise(suits): Since only two elements from suits are considered at a time, the extra space is O(1).

  3. No additional data structures with significant space requirements are used.

Like the time complexity, as the hand size is fixed, m can be considered a constant, simplifying the space complexity to O(1).

Overall, both the time and space complexities for this code can effectively be considered constant, O(1), under the assumption of a fixed-size hand in a card game.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used to implement priority queue?


Recommended Readings


Got a question? Ask the Monster 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.


🪄