2347. Best Poker Hand
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:
-
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 convertingsuits
into a set, which has a time complexity of O(n), an optimized approach checkingall(a == b for a, b in pairwise(suits))
is used. This uses thepairwise
function from Python'sitertools
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 thecollections
module. TheCounter
object,cnt
, maps each rank to the number of times it appears in theranks
list.
- Flush Check: To identify a "Flush," we're looking for the uniqueness of suits. If all suits are the same, the set of
-
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.
- The checks are done in a particular order, from the best hand to the worst. This is done using a series of
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.
class Solution:
def bestHand(self, ranks: List[int], suits: List[str]) -> str:
# Check for Flush
if all(a == b for a, b in pairwise(suits)):
return 'Flush'
cnt = Counter(ranks)
# Check for Three of a Kind
if any(v >= 3 for v in cnt.values()):
return 'Three of a Kind'
# Check for Pair
if any(v == 2 for v in cnt.values()):
return 'Pair'
# If none of the above, return High Card
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
-
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.
-
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.
- We find that the rank 10 appears twice (
- Create a frequency count of the ranks using
-
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:
-
all(a == b for a, b in pairwise(suits))
: This checks if all elements insuits
are the same. Assumingpairwise
is an iterable that provides tuples of successive pairs fromsuits
, this operation has a time complexity ofO(n)
, wheren
is the number of suits. -
Counter(ranks)
: Counting the frequency of each rank has a time complexity ofO(m)
, wherem
is the number of ranks. -
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 ofO(m)
. -
any(v == 2 for v in cnt.values())
: Similarly, this check for a 'Pair' has a time complexity ofO(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:
-
Counter(ranks)
: The counter here creates a dictionary with a unique entry for each rank. The space complexity isO(m)
since it stores as many entries as there are unique ranks. -
Temporal space needed to store the pairs in
pairwise(suits)
: Since only two elements fromsuits
are considered at a time, the extra space isO(1)
. -
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.
The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!