Straight Hand in Poker

Overview

The problem asks us to determine if five unique cards form a straight. A straight consists of five cards with consecutive numerical values. The primary challenge lies in handling non-numeric faces (J, Q, K, A) and the dual nature of the Ace, which can serve as the lowest value ($1$) or the highest value ($14$).

Since the input size is fixed at $N=5$, the main task is to map these strings to integers, sort them, and check for a continuous range.

Brute Force

The brute force approach involves generating the two possible integer interpretations of the hand (one where A=1 and one where A=14) and checking if either set of values forms a consecutive sequence after sorting.

1. Create a mapping for faces: {"J": 11, "Q": 12, "K": 13}.
2. For the Ace, create two versions of the input list:
   • Version A: A is mapped to 1.
   • Version B: A is mapped to 14.
3. For each version, sort the numbers.
4. Check if the numbers are consecutive: all(arr[i] + 1 == arr[i+1] for i in range(4)).
5. If either version returns true, the hand is a straight.

def is_straight(cards: list[str]) -> bool:
    def check(values):
        values.sort()
        for i in range(len(values) - 1):
            if values[i] + 1 != values[i + 1]:
                return False
        return True

    mapping = {
        "2": 2, "3": 3, "4": 4, "5": 5, "6": 6, "7": 7, 
        "8": 8, "9": 9, "10": 10, "J": 11, "Q": 12, "K": 13
    }
    
    # Case 1: Ace is 1
    hand_low = [mapping[c] if c != "A" else 1 for c in cards]
    if check(hand_low):
        return True
        
    # Case 2: Ace is 14
    hand_high = [mapping[c] if c != "A" else 14 for c in cards]
    if check(hand_high):
        return True
        
    return False

Time complexity: O(1) — Since the input size is strictly fixed at 5, sorting and iteration happen in constant time. Space complexity: O(1) — We store a fixed mapping and two lists of 5 integers.

Optimal Approach

The optimal approach simplifies the logic by focusing on the mathematical properties of a straight. In any sequence of 5 unique consecutive numbers, the difference between the maximum and minimum value must be exactly 4.

However, the Ace's dual role still requires a special check. The only time an Ace is "low" ($1$) is in the specific sequence A-2-3-4-5. In all other straights involving an Ace (like 10-J-Q-K-A), the Ace acts as $14$.

1. Map all cards to their "high" values: {"A": 14, "2": 2, ..., "K": 13}.
2. Check for the special "Baby Straight" (A, 2, 3, 4, 5). If the set of values is exactly {14, 2, 3, 4, 5}, return True.
3. For all other cases, find the max_val and min_val in the numeric set.
4. If max_val - min_val == 4, return True. (Note: This works because the problem guarantees all cards are unique).

def is_straight(cards: list[str]) -> bool:
    rank_map = {
        "2": 2, "3": 3, "4": 4, "5": 5, "6": 6, "7": 7, "8": 8, 
        "9": 9, "10": 10, "J": 11, "Q": 12, "K": 13, "A": 14
    }
    
    # Convert input to set of integers using 'High' Ace values
    ranks = {rank_map[c] for c in cards}
    
    # Special case: Baby Straight (A, 2, 3, 4, 5)
    # Since we mapped A to 14, we check for {14, 2, 3, 4, 5}
    if ranks == {14, 2, 3, 4, 5}:
        return True
        
    # Standard case: Difference between max and min must be 4
    return max(ranks) - min(ranks) == 4

Time complexity: O(1) — We perform a single pass over 5 cards to create a set and find the min/max. Space complexity: O(1) — The set and map sizes are constant.

Why this works

In any set of $N$ unique integers, if the range ($\text{max} - \text{min}$) is equal to $N-1$, the integers must be consecutive.

• Example: {7, 8, 9, 10, 11} $\rightarrow$ $11 - 7 = 4$.
• Example: {7, 8, 10, 11, 12} $\rightarrow$ $12 - 7 = 5$ (Gap detected).

Because we are told the cards are unique, we don't need to worry about hands like [2, 2, 3, 4, 6], which would have a range of 4 but are not a straight.

Fast