846. Hand of Straights

📝 Problem Details

• Title: 846. Hand of Straights
• Link: https://leetcode.com/problems/hand-of-straights/
• Difficulty: Medium
• Tags/Categories: Greedy Hashmap Sorting

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

input integer groupSize input array hand where hand[i] is the value written on the card return true if she can rearrange the cards

💡 Explanation of Solution

1. Count the occurrences of each card using a frequency hashmap
2. Iterate through the sorted hand to try to form groups starting from the smallest card
3. If we find a missing card in a group, return false
4. Reduce the frequency of used cards

⌛ Complexity Analysis

Time Complexity: O(n log n) for maintaining sorted order of elements in the ordered map

Space Complexity: O(n)

💻 Implementation of Solution

class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int groupSize) {
        if (hand.size() % groupSize != 0) return false; // Early exit if total cards aren't divisible
 
        map<int, int> freq; // Keeps card counts sorted
        for (int card : hand) {
            freq[card]++;
        }
 
        for (auto [card, count] : freq) {
            if (count > 0) { // If we still have cards left to use
                int needed = count; // We must create `needed` full groups
                for (int i = 0; i < groupSize; i++) {
                    if (freq[card + i] < needed) return false; // Not enough cards to form a group
                    freq[card + i] -= needed; // Use these cards
                }
            }
        }
        return true;
    }
};