algoadvance

Leetcode 846. Hand of Straights

Problem Statement

You are given an integer array hand of size N where hand[i] represents the rank of the ith card. You are also given an integer groupSize which represents the size of each group you want to divide the cards into.

You need to determine if it is possible to rearrange the cards in such a way that they can be grouped into sets of groupSize with consecutive cards. If it is possible, return true, otherwise return false.

Example:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Possible to reorder into groups: [1,2,3], [2,3,4], [6,7,8]

Input: hand = [1,2,3,4,5], groupSize = 4
Output: false
Explanation: Cannot form groups of 4 with consecutive cards.

Clarifying Questions

1. Range of Values in hand: Are there any constraints on the possible values of the cards?
   • Assumption: The range of values in hand is not constrained but will contain a reasonably large set of numbers.
2. Unique Cards: Can we assume that each group of consecutive cards is unique?
   • Assumption: No, there may be duplicates and the same card value can appear multiple times in different groups.
3. Order of Groups: Does the order in which the groups are formed matter?
   • Assumption: No, the order does not matter as long as all cards can be grouped.

Strategy

1. Check for Immediate Impossibility: If N % groupSize != 0, it is immediately impossible to form the required groups.
2. Frequency Map: Use a frequency map (hash map) to count the occurrences of each card.
3. Iterate and Form Groups: Iterate through the sorted keys of the frequency map and try to form groups by ensuring that consecutive cards are available in sufficient quantity.
4. Decrease Frequencies: Decrease the count of each card used to form a group.
5. Early Termination: If at any point a card needed to complete a group is not available in sufficient quantity, return false.

Code

#include <vector>
#include <map>
#include <algorithm>

bool isNStraightHand(std::vector<int>& hand, int groupSize) {
    if (hand.size() % groupSize != 0)
        return false;
    
    std::map<int, int> frequency;
    for (int card : hand) {
        frequency[card]++;
    }
    
    for (const auto& entry : frequency) {
        int startCard = entry.first;
        int count = entry.second;
        
        if (count > 0) {
            for (int i = 1; i < groupSize; ++i) {
                if (frequency[startCard + i] < count)
                    return false;
                frequency[startCard + i] -= count;
            }
        }
    }
    
    return true;
}

Time Complexity

• Sorting the hand takes O(N log N) where (N) is the number of cards.
• Iterating through the sorted keys and forming groups takes O(N \cdot groupSize) in the worst case, but since the size of each consecutive segment is bounded by groupSize, this can be considered O(N).
• Overall, the time complexity is dominated by the sorting step: O(N log N).

This solution ensures we efficiently determine if the hand can be rearranged into groups of the specified size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?