Jobs

Interviews

Discussions

Best Poker Hand

Easy

Amazon

3 views

Topics:

ArraysStrings

You are given an integer array ranks and a character array suits. You have 5 cards where the i<sup>th</sup> card has a rank of ranks[i] and a suit of suits[i].

The following are the types of poker hands you can make from best to worst:

"Flush": Five cards of the same suit.
"Three of a Kind": Three cards of the same rank.
"Pair": Two cards of the same rank.
"High Card": Any single card.

Return a string representing the best type of poker hand you can make with the given cards.

Examples:

Input: ranks = [13,2,3,1,9], suits = ["a","a","a","a","a"] Output: "Flush"
Input: ranks = [4,4,2,4,4], suits = ["d","a","a","b","c"] Output: "Three of a Kind"
Input: ranks = [10,10,2,12,9], suits = ["a","b","c","a","d"] Output: "Pair"

Write a function to efficiently determine the best poker hand based on the provided ranks and suits. Consider various edge cases and optimize for both time and space complexity.

Best Poker Hand

Easy

Amazon

3 views

Topics:

ArraysStrings

You are given an integer array ranks and a character array suits. You have 5 cards where the i<sup>th</sup> card has a rank of ranks[i] and a suit of suits[i].

The following are the types of poker hands you can make from best to worst:

"Flush": Five cards of the same suit.
"Three of a Kind": Three cards of the same rank.
"Pair": Two cards of the same rank.
"High Card": Any single card.

Return a string representing the best type of poker hand you can make with the given cards.

Examples:

Input: ranks = [13,2,3,1,9], suits = ["a","a","a","a","a"] Output: "Flush"
Input: ranks = [4,4,2,4,4], suits = ["d","a","a","b","c"] Output: "Three of a Kind"
Input: ranks = [10,10,2,12,9], suits = ["a","b","c","a","d"] Output: "Pair"

Write a function to efficiently determine the best poker hand based on the provided ranks and suits. Consider various edge cases and optimize for both time and space complexity.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible values for the ranks and suits, and are they represented as strings or numbers?
Is the input guaranteed to be valid, meaning will I always receive exactly 5 cards, and will the suits and ranks always be legal?
If multiple poker hands have the same highest rank (e.g., two flushes), should I return either one or is there a tie-breaking rule?
Are the input arrays (ranks and suits) guaranteed to be non-null and of the same length?
What is the expected behavior if there's an invalid input, such as an empty array or different lengths for ranks and suits?

Brute Force Solution

Approach

The brute force approach to finding the best poker hand involves checking every possible hand combination you could form from the given cards. We evaluate each combination according to the rules of poker, determining the rank of each possible hand. Finally, we identify the hand with the highest rank among all the checked combinations.

Here's how the algorithm would work step-by-step:

Consider every possible combination of cards from the input.
For each combination, determine what type of poker hand it is (e.g., flush, straight, pair).
Compare each poker hand against the other poker hands.
Determine the strongest poker hand amongst them.
Return the strongest poker hand

Code Implementation

def best_poker_hand(ranks, suits):    all_cards = list(zip(ranks, suits))
    best_hand = "High Card"
    card_values = {'2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9, 'T': 10, 'J': 11, 'Q': 12, 'K': 13, 'A': 14}
    numeric_ranks = [card_values[rank] for rank in ranks]

    # Check for flush
    if len(set(suits)) == 1:
        best_hand = "Flush"
        numeric_ranks.sort()
        # Check for straight flush
        if numeric_ranks == list(range(numeric_ranks[0], numeric_ranks[0] + 5)):
            best_hand = "Straight Flush"
            # Check for royal flush
            if numeric_ranks[0] == 10:
                best_hand = "Royal Flush"
        return best_hand

    rank_counts = {}
    for rank in ranks:
        rank_counts[rank] = rank_counts.get(rank, 0) + 1

    # Check for four of a kind
    if 4 in rank_counts.values():
        return "Four of a Kind"

    # Check for full house
    if 3 in rank_counts.values() and 2 in rank_counts.values():
        return "Full House"

    numeric_ranks.sort()
    # Check for straight
    if len(set(numeric_ranks)) == 5 and numeric_ranks[-1] - numeric_ranks[0] == 4:
        return "Straight"

    # Check for three of a kind
    if 3 in rank_counts.values():
        return "Three of a Kind"

    pair_count = sum(1 for count in rank_counts.values() if count == 2)

    # Check for two pair
    if pair_count == 2:
        return "Two Pair"

    # Check for pair
    if pair_count == 1:
        return "Pair"

    return best_hand

Big(O) Analysis

Time Complexity

O(1) – The problem specifies that we are always given exactly 5 cards. Therefore, the number of combinations and the operations performed to evaluate and compare poker hands remains constant regardless of any input 'n'. Because the input size is fixed, the runtime does not scale with any variable input, and it takes constant time O(1).

Space Complexity

O(1) – The brute force approach described checks every possible combination of cards and compares the poker hands. While checking each combination, we need a few variables to track the rank of the current hand. No auxiliary data structures scale with the input size N (where N represents the total number of cards). Therefore, the algorithm uses a constant amount of extra space.

Optimal Solution

Approach

To find the best poker hand, we need to check for the strongest hand first and work our way down. This avoids unnecessary checks. We can use counting to determine which hand is present without exhaustively comparing every card combination.

Here's how the algorithm would work step-by-step:

First, check if the hand is a flush, meaning all cards have the same suit.
Then, check if the hand is a straight, meaning the card values are in sequence. Consider the Ace as both the highest and lowest card.
If both a flush and a straight are true, check for a straight flush, and if the straight flush starts with a ten, it's a royal flush, the best possible hand.
If it is not a straight flush, count how many times each card value appears in the hand.
Based on these counts, identify four of a kind, three of a kind, pairs, and high card.
After checking the possibilities in decreasing order of hand rank return the best poker hand based on the checks.

Code Implementation

def best_poker_hand(ranks, suits):
    is_flush = len(set(suits)) == 1

    rank_values = {'2':2, '3':3, '4':4, '5':5, '6':6, '7':7,
                   '8':8, '9':9, 'T':10, 'J':11, 'Q':12, 'K':13, 'A':14}
    numerical_ranks = sorted([rank_values[rank] for rank in ranks])

    is_straight = (numerical_ranks == list(range(numerical_ranks[0], numerical_ranks[0] + 5)) or
                   numerical_ranks == [2, 3, 4, 5, 14])

    if is_flush and is_straight:
        if numerical_ranks == [10, 11, 12, 13, 14]:
            return "Royal Flush"
        return "Straight Flush"

    rank_counts = {}
    for rank in ranks:
        rank_counts[rank] = rank_counts.get(rank, 0) + 1

    # Determine the type of hand based on rank counts.
    if 5 in rank_counts.values():
        return "Four of a Kind" # Should be invalid given prior checks

    if 4 in rank_counts.values():
        return "Four of a Kind"

    if 3 in rank_counts.values() and 2 in rank_counts.values():
        return "Full House"

    if is_flush:
        return "Flush"

    if is_straight:
        return "Straight"

    if 3 in rank_counts.values():
        return "Three of a Kind"

    pair_count = sum(1 for count in rank_counts.values() if count == 2)

    if pair_count == 2:
        return "Two Pair"

    if pair_count == 1:
        return "One Pair"

    # If none of the above, return high card.
    return "High Card"

Big(O) Analysis

Time Complexity

O(n) – Determining the best poker hand involves several steps. Checking for a flush requires iterating through the cards once (O(n)). Checking for a straight and counting card values both also require iterating through the cards once (O(n)). Identifying the hand based on card counts involves a fixed number of comparisons. Since all operations iterate through the 5 cards in the hand a constant number of times, the overall time complexity is O(n), where n is the number of cards in the hand, which is constant at 5.

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. Specifically, the algorithm checks for flushes and straights without creating any data structures that scale with the input size. The counting of card values involves storing frequencies in fixed-size containers (e.g., an array or hash map of size at most 13, since there are 13 possible card values). The number of variables used to store intermediate results and flags (like flush or straight) remains constant, independent of the number of cards in hand. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input ranks or suits arrays	Return 'None' as no hand can be evaluated without cards.
Mismatched lengths of ranks and suits arrays	Throw an IllegalArgumentException or return 'Error' since the arrays must represent a consistent hand.
Ranks array contains invalid rank values (e.g., outside 2-14 range if using integers)	Filter out invalid ranks or throw an IllegalArgumentException.
Suits array contains invalid suit values (e.g., not 'a', 'b', 'c', 'd')	Filter out invalid suits or throw an IllegalArgumentException.
All cards are the same rank (e.g., five 2s)	Correctly identifies as a 'Three of a Kind', 'Pair', or 'High Card' as appropriate.
All cards are the same suit, but not a straight	Detect Flush correctly even when not a straight.
A straight flush is present	Prioritize and return 'Straight Flush' appropriately.
Input hand contains duplicate cards (same rank and suit)	Return 'Error' or 'Invalid Hand', as poker hands should not contain duplicates.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible values for the ranks and suits, and are they represented as strings or numbers?
Is the input guaranteed to be valid, meaning will I always receive exactly 5 cards, and will the suits and ranks always be legal?
If multiple poker hands have the same highest rank (e.g., two flushes), should I return either one or is there a tie-breaking rule?
Are the input arrays (ranks and suits) guaranteed to be non-null and of the same length?
What is the expected behavior if there's an invalid input, such as an empty array or different lengths for ranks and suits?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider every possible combination of cards from the input.
For each combination, determine what type of poker hand it is (e.g., flush, straight, pair).
Compare each poker hand against the other poker hands.
Determine the strongest poker hand amongst them.
Return the strongest poker hand

Code Implementation

def best_poker_hand(ranks, suits):    all_cards = list(zip(ranks, suits))
    best_hand = "High Card"
    card_values = {'2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9, 'T': 10, 'J': 11, 'Q': 12, 'K': 13, 'A': 14}
    numeric_ranks = [card_values[rank] for rank in ranks]

    # Check for flush
    if len(set(suits)) == 1:
        best_hand = "Flush"
        numeric_ranks.sort()
        # Check for straight flush
        if numeric_ranks == list(range(numeric_ranks[0], numeric_ranks[0] + 5)):
            best_hand = "Straight Flush"
            # Check for royal flush
            if numeric_ranks[0] == 10:
                best_hand = "Royal Flush"
        return best_hand

    rank_counts = {}
    for rank in ranks:
        rank_counts[rank] = rank_counts.get(rank, 0) + 1

    # Check for four of a kind
    if 4 in rank_counts.values():
        return "Four of a Kind"

    # Check for full house
    if 3 in rank_counts.values() and 2 in rank_counts.values():
        return "Full House"

    numeric_ranks.sort()
    # Check for straight
    if len(set(numeric_ranks)) == 5 and numeric_ranks[-1] - numeric_ranks[0] == 4:
        return "Straight"

    # Check for three of a kind
    if 3 in rank_counts.values():
        return "Three of a Kind"

    pair_count = sum(1 for count in rank_counts.values() if count == 2)

    # Check for two pair
    if pair_count == 2:
        return "Two Pair"

    # Check for pair
    if pair_count == 1:
        return "Pair"

    return best_hand

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, check if the hand is a flush, meaning all cards have the same suit.
Then, check if the hand is a straight, meaning the card values are in sequence. Consider the Ace as both the highest and lowest card.
If both a flush and a straight are true, check for a straight flush, and if the straight flush starts with a ten, it's a royal flush, the best possible hand.
If it is not a straight flush, count how many times each card value appears in the hand.
Based on these counts, identify four of a kind, three of a kind, pairs, and high card.
After checking the possibilities in decreasing order of hand rank return the best poker hand based on the checks.

Code Implementation

def best_poker_hand(ranks, suits):
    is_flush = len(set(suits)) == 1

    rank_values = {'2':2, '3':3, '4':4, '5':5, '6':6, '7':7,
                   '8':8, '9':9, 'T':10, 'J':11, 'Q':12, 'K':13, 'A':14}
    numerical_ranks = sorted([rank_values[rank] for rank in ranks])

    is_straight = (numerical_ranks == list(range(numerical_ranks[0], numerical_ranks[0] + 5)) or
                   numerical_ranks == [2, 3, 4, 5, 14])

    if is_flush and is_straight:
        if numerical_ranks == [10, 11, 12, 13, 14]:
            return "Royal Flush"
        return "Straight Flush"

    rank_counts = {}
    for rank in ranks:
        rank_counts[rank] = rank_counts.get(rank, 0) + 1

    # Determine the type of hand based on rank counts.
    if 5 in rank_counts.values():
        return "Four of a Kind" # Should be invalid given prior checks

    if 4 in rank_counts.values():
        return "Four of a Kind"

    if 3 in rank_counts.values() and 2 in rank_counts.values():
        return "Full House"

    if is_flush:
        return "Flush"

    if is_straight:
        return "Straight"

    if 3 in rank_counts.values():
        return "Three of a Kind"

    pair_count = sum(1 for count in rank_counts.values() if count == 2)

    if pair_count == 2:
        return "Two Pair"

    if pair_count == 1:
        return "One Pair"

    # If none of the above, return high card.
    return "High Card"

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input ranks or suits arrays	Return 'None' as no hand can be evaluated without cards.
Mismatched lengths of ranks and suits arrays	Throw an IllegalArgumentException or return 'Error' since the arrays must represent a consistent hand.
Ranks array contains invalid rank values (e.g., outside 2-14 range if using integers)	Filter out invalid ranks or throw an IllegalArgumentException.
Suits array contains invalid suit values (e.g., not 'a', 'b', 'c', 'd')	Filter out invalid suits or throw an IllegalArgumentException.
All cards are the same rank (e.g., five 2s)	Correctly identifies as a 'Three of a Kind', 'Pair', or 'High Card' as appropriate.
All cards are the same suit, but not a straight	Detect Flush correctly even when not a straight.
A straight flush is present	Prioritize and return 'Straight Flush' appropriately.
Input hand contains duplicate cards (same rank and suit)	Return 'Error' or 'Invalid Hand', as poker hands should not contain duplicates.