Jobs

Interviews

Discussions

Hand of Straights

Medium

Asked by:

More companies

33 views

Topics:

ArraysGreedy Algorithms

Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards.

Given an integer array hand where hand[i] is the value written on the i^th card and an integer groupSize, return true if she can rearrange the cards, or false otherwise.

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]

Example 2:

Input: hand = [1,2,3,4,5], groupSize = 4
Output: false
Explanation: Alice's hand can not be rearranged into groups of 4.

Constraints:

1 <= hand.length <= 10⁴
0 <= hand[i] <= 10⁹
1 <= groupSize <= hand.length

Note: This question is the same as 1296: https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/

Try coding it in LeetCode

Hand of Straights

Medium

Asked by:

33 views

Topics:

ArraysGreedy Algorithms

Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards.

Given an integer array hand where hand[i] is the value written on the i^th card and an integer groupSize, return true if she can rearrange the cards, or false otherwise.

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]

Example 2:

Input: hand = [1,2,3,4,5], groupSize = 4
Output: false
Explanation: Alice's hand can not be rearranged into groups of 4.

Constraints:

1 <= hand.length <= 10⁴
0 <= hand[i] <= 10⁹
1 <= groupSize <= hand.length

Note: This question is the same as 1296: https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/

Try coding it in LeetCode

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:

Can the input array `hand` contain duplicate numbers, and if so, how should they be handled?
Can the values in the `hand` array be negative or zero?
If it's impossible to divide the hand into groups of size `groupSize`, what should I return (e.g., `false`, `null`, throw an exception)?
What is the expected range of values for numbers in the `hand` array?
Is the `groupSize` always a positive integer, and is it always less than or equal to the size of the `hand` array?

Brute Force Solution

Approach

The brute force approach to determining if a hand of cards can be arranged into groups of consecutive cards involves checking all possible combinations. We attempt to build groups card by card, seeing if any combination works. If a solution is found, we are done.

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

First, check if we even have enough cards to make complete groups of the required size. If not, it's impossible.
Pick any card from the hand to start forming a potential group.
Try to find the next consecutive card needed to continue building the group. If it exists, add it to the group.
Keep adding consecutive cards until the group is complete or you can't find the next consecutive card.
If you couldn't complete the group, start over with a different card as the potential start of a group.
If you did complete a group, remove those cards from the hand and repeat the process with the remaining cards.
If you manage to form all the cards into complete groups, you have found a valid arrangement. If you exhaust all possibilities of picking a starting card and forming groups without completing all groups, it's not possible to arrange the cards as requested.

Code Implementation

def can_arrange_into_groups_brute_force(hand, group_size):
    number_of_cards = len(hand)
    if number_of_cards % group_size != 0:
        return False

    def can_form_groups(current_hand):
        if not current_hand:
            return True

        # Try each card as the start of a group
        for start_card in list(current_hand):
            potential_group = [start_card]
            remaining_hand = list(current_hand)
            remaining_hand.remove(start_card)
            
            # Attempt to build the group
            for _ in range(group_size - 1):
                next_card = potential_group[-1] + 1
                if next_card in remaining_hand:
                    potential_group.append(next_card)
                    remaining_hand.remove(next_card)
                else:
                    break

            # If the group is complete, proceed recursively
            if len(potential_group) == group_size:

                # Recursively check if the remaining cards can form groups
                if can_form_groups(remaining_hand):
                    return True
        
        # No valid group found
        return False

    return can_form_groups(hand)

Big(O) Analysis

Time Complexity

O((n/k) * n * k) – Let n be the total number of cards and k be the group size. The outermost loop iterates at most n/k times since we're trying to form that many groups. Within each potential group formation, we iterate through the remaining cards (at most n) to find consecutive cards. For each card, finding a consecutive card takes at most k iterations. Therefore, the total operations can be approximated as (n/k) * n * k, which simplifies to O(n²).

Space Complexity

O(N) – The brute force approach, as described, attempts to build groups and removes cards from the hand. The most significant space usage comes from needing to create copies of the hand or marking cards as used to avoid modifying the original input during the search for consecutive cards. In the worst case, where no valid arrangement is found until most combinations are checked, we might effectively need to maintain a working copy of the hand, which could contain up to N cards, where N is the total number of cards. Therefore, the space complexity is O(N).

Optimal Solution

Approach

The best approach to this problem is to efficiently build sets of consecutive numbers. We focus on finding the smallest number and using it as the starting point for a potential straight. We then try to construct a complete straight from that starting point.

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

First, we need to know how many numbers are in each straight we're trying to build. This is important because it tells us the size of each group we're aiming for.
Organize the numbers we're given so that we can easily find the smallest one. Think of sorting them or putting them into a special container that automatically keeps them in order.
Now, repeatedly pick the smallest number. This number is the potential start of a new straight.
See if you can build a complete straight starting from that smallest number. This means checking if the next number in the straight is available, then the number after that, and so on, until you have the full straight.
If you can build the straight, remove those numbers from the collection of available numbers. If you can't, then it is impossible to form the 'hand of straights'.
Keep repeating the process of finding the smallest number and trying to build a straight until you've used up all the numbers.
If you successfully build all the straights without any leftover numbers, then it's possible to make the hand of straights.

Code Implementation

def is_straight_hand(hand, group_size):
    if len(hand) % group_size != 0:
        return False

    hand_map = {}
    for card in hand:
        hand_map[card] = hand_map.get(card, 0) + 1

    hand.sort()

    for card in hand:
        if hand_map.get(card, 0) > 0:
            # We found the potential start of a new straight
            start_card = card

            # Attempt to build a complete straight from this starting point
            for i in range(group_size):
                required_card = start_card + i
                if hand_map.get(required_card, 0) > 0:
                    hand_map[required_card] -= 1
                    if hand_map[required_card] == 0:
                        del hand_map[required_card]
                else:
                    # It's not possible to make the hand of straights
                    return False

    # If we made it here, we successfully built all straights
    return True

Big(O) Analysis

Time Complexity

O(n log n) – The initial sorting of the hand takes O(n log n) time, where n is the number of cards. We iterate through the sorted hand, finding the smallest number in O(1) time using a sorted data structure like a TreeMap or a heap. For each smallest number, we attempt to build a straight of size groupSize. Building the straight involves removing elements, each taking O(log n) time with a TreeMap or O(1) amortized time with a hash map used with a separate sorted list (but this would complicate maintaining sorted order). Since we build n / groupSize straights and each straight construction takes groupSize * O(log n) (or groupSize * O(1)) time for removals, the total time complexity is dominated by the initial sort, hence O(n log n).

Space Complexity

O(N) – The provided explanation suggests organizing the numbers to easily find the smallest, implying the use of a sorted data structure or a min-heap. If a sorted data structure like an array or list is used, it would require auxiliary space proportional to the input size N, where N is the number of cards in the hand. Alternatively, a hash map to count the frequencies of each number would also require O(N) space. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
hand is null or empty	Return false immediately, as a hand cannot be formed.
groupSize is zero or negative	Throw an IllegalArgumentException, as a group size must be positive.
hand's length is not divisible by groupSize	Return false, because we cannot form complete groups of the specified size.
hand contains negative numbers	The sorting and subsequent checks should handle negative numbers correctly as long as arithmetic operations don't overflow.
hand contains duplicate numbers making straights impossible	Count the occurrences of each number and if we can't create enough groups of `groupSize` we return false.
groupSize is equal to hand's length	Check if the sorted hand forms a single straight of length hand.length.
Large input array size causing memory issues	Consider using an efficient data structure like a TreeMap to reduce memory footprint, and carefully consider arithmetic overflow in calculations.
hand contains Integer.MAX_VALUE and groupSize > 1	Handle potential integer overflow when checking consecutive numbers by using long for intermediate calculations or carefully checking for overflow conditions.

hand is null or empty

How to Handle:

Return false immediately, as a hand cannot be formed.

groupSize is zero or negative

How to Handle:

Throw an IllegalArgumentException, as a group size must be positive.

hand's length is not divisible by groupSize

How to Handle:

Return false, because we cannot form complete groups of the specified size.

hand contains negative numbers

How to Handle:

The sorting and subsequent checks should handle negative numbers correctly as long as arithmetic operations don't overflow.

hand contains duplicate numbers making straights impossible

How to Handle:

Count the occurrences of each number and if we can't create enough groups of `groupSize` we return false.

groupSize is equal to hand's length

How to Handle:

Check if the sorted hand forms a single straight of length hand.length.

Large input array size causing memory issues

How to Handle:

Consider using an efficient data structure like a TreeMap to reduce memory footprint, and carefully consider arithmetic overflow in calculations.

hand contains Integer.MAX_VALUE and groupSize > 1

How to Handle:

Handle potential integer overflow when checking consecutive numbers by using long for intermediate calculations or carefully checking for overflow conditions.

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:

Can the input array `hand` contain duplicate numbers, and if so, how should they be handled?
Can the values in the `hand` array be negative or zero?
If it's impossible to divide the hand into groups of size `groupSize`, what should I return (e.g., `false`, `null`, throw an exception)?
What is the expected range of values for numbers in the `hand` array?
Is the `groupSize` always a positive integer, and is it always less than or equal to the size of the `hand` array?

Brute Force Solution

Approach

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

First, check if we even have enough cards to make complete groups of the required size. If not, it's impossible.
Pick any card from the hand to start forming a potential group.
Try to find the next consecutive card needed to continue building the group. If it exists, add it to the group.
Keep adding consecutive cards until the group is complete or you can't find the next consecutive card.
If you couldn't complete the group, start over with a different card as the potential start of a group.
If you did complete a group, remove those cards from the hand and repeat the process with the remaining cards.
If you manage to form all the cards into complete groups, you have found a valid arrangement. If you exhaust all possibilities of picking a starting card and forming groups without completing all groups, it's not possible to arrange the cards as requested.

Code Implementation

def can_arrange_into_groups_brute_force(hand, group_size):
    number_of_cards = len(hand)
    if number_of_cards % group_size != 0:
        return False

    def can_form_groups(current_hand):
        if not current_hand:
            return True

        # Try each card as the start of a group
        for start_card in list(current_hand):
            potential_group = [start_card]
            remaining_hand = list(current_hand)
            remaining_hand.remove(start_card)
            
            # Attempt to build the group
            for _ in range(group_size - 1):
                next_card = potential_group[-1] + 1
                if next_card in remaining_hand:
                    potential_group.append(next_card)
                    remaining_hand.remove(next_card)
                else:
                    break

            # If the group is complete, proceed recursively
            if len(potential_group) == group_size:

                # Recursively check if the remaining cards can form groups
                if can_form_groups(remaining_hand):
                    return True
        
        # No valid group found
        return False

    return can_form_groups(hand)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, we need to know how many numbers are in each straight we're trying to build. This is important because it tells us the size of each group we're aiming for.
Organize the numbers we're given so that we can easily find the smallest one. Think of sorting them or putting them into a special container that automatically keeps them in order.
Now, repeatedly pick the smallest number. This number is the potential start of a new straight.
See if you can build a complete straight starting from that smallest number. This means checking if the next number in the straight is available, then the number after that, and so on, until you have the full straight.
If you can build the straight, remove those numbers from the collection of available numbers. If you can't, then it is impossible to form the 'hand of straights'.
Keep repeating the process of finding the smallest number and trying to build a straight until you've used up all the numbers.
If you successfully build all the straights without any leftover numbers, then it's possible to make the hand of straights.

Code Implementation

def is_straight_hand(hand, group_size):
    if len(hand) % group_size != 0:
        return False

    hand_map = {}
    for card in hand:
        hand_map[card] = hand_map.get(card, 0) + 1

    hand.sort()

    for card in hand:
        if hand_map.get(card, 0) > 0:
            # We found the potential start of a new straight
            start_card = card

            # Attempt to build a complete straight from this starting point
            for i in range(group_size):
                required_card = start_card + i
                if hand_map.get(required_card, 0) > 0:
                    hand_map[required_card] -= 1
                    if hand_map[required_card] == 0:
                        del hand_map[required_card]
                else:
                    # It's not possible to make the hand of straights
                    return False

    # If we made it here, we successfully built all straights
    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
hand is null or empty	Return false immediately, as a hand cannot be formed.
groupSize is zero or negative	Throw an IllegalArgumentException, as a group size must be positive.
hand's length is not divisible by groupSize	Return false, because we cannot form complete groups of the specified size.
hand contains negative numbers	The sorting and subsequent checks should handle negative numbers correctly as long as arithmetic operations don't overflow.
hand contains duplicate numbers making straights impossible	Count the occurrences of each number and if we can't create enough groups of `groupSize` we return false.
groupSize is equal to hand's length	Check if the sorted hand forms a single straight of length hand.length.
Large input array size causing memory issues	Consider using an efficient data structure like a TreeMap to reduce memory footprint, and carefully consider arithmetic overflow in calculations.
hand contains Integer.MAX_VALUE and groupSize > 1	Handle potential integer overflow when checking consecutive numbers by using long for intermediate calculations or carefully checking for overflow conditions.

hand is null or empty

How to Handle:

Return false immediately, as a hand cannot be formed.

groupSize is zero or negative

How to Handle:

Throw an IllegalArgumentException, as a group size must be positive.

hand's length is not divisible by groupSize

How to Handle:

Return false, because we cannot form complete groups of the specified size.

hand contains negative numbers

How to Handle:

The sorting and subsequent checks should handle negative numbers correctly as long as arithmetic operations don't overflow.

hand contains duplicate numbers making straights impossible

How to Handle:

Count the occurrences of each number and if we can't create enough groups of `groupSize` we return false.

groupSize is equal to hand's length

How to Handle:

Check if the sorted hand forms a single straight of length hand.length.

Large input array size causing memory issues

How to Handle:

Consider using an efficient data structure like a TreeMap to reduce memory footprint, and carefully consider arithmetic overflow in calculations.

hand contains Integer.MAX_VALUE and groupSize > 1

How to Handle:

Handle potential integer overflow when checking consecutive numbers by using long for intermediate calculations or carefully checking for overflow conditions.