Hand of Straights medium

Problem Statement

You are given an integer array hand containing integers from 1 to W, where W is the number of unique values in hand. You are also given an integer W representing the number of unique values in the hand. You need to determine if it is possible to partition the cards into groups of size groupSize such that each group is a consecutive sequence.

For example, if hand = [1,2,3,6,2,3,4,7,5] and groupSize = 3, then we can partition the cards into groups [1,2,3], [2,3,4], [5,6,7]. If groupSize = 4, it's impossible.

Example 1

Input: hand = [1,2,3,6,2,3,4,7,5], groupSize = 3 Output: true Explanation: We can partition the cards into groups [1,2,3], [2,3,4], [5,6,7].

Example 2

Input: hand = [1,2,3,4,5], groupSize = 4 Output: false Explanation: We can't partition the cards into groups of size 4.

Steps

1. Frequency Counting: Create a dictionary (or hash map) to count the frequency of each card in the hand.
2. Iteration and Check: Iterate through the sorted unique card values. For each card, check if we have enough cards to form a group of size groupSize.
3. Group Formation: If we have enough cards, decrement the frequency of the current card and all subsequent consecutive cards in the group.
4. Impossible Condition: If at any point we don't have enough cards for a consecutive value, it's impossible to form hands, and we return false.
5. Success Condition: If we successfully process all cards, it's possible to form hands, and we return true.

Explanation

The key idea is to efficiently manage the frequency of cards and check for consecutive sequences. Using a dictionary avoids the need to sort the entire hand, improving efficiency. The sorted order of iteration ensures that we always try to form groups with the smallest possible values first, preventing unnecessary backtracking.

Code

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public bool IsNStraightHand(int[] hand, int groupSize) {
        if (hand.Length % groupSize != 0) return false; // Impossible if length isn't a multiple of groupSize

        Dictionary<int, int> counts = new Dictionary<int, int>();
        foreach (int card in hand) {
            counts[card] = counts.GetValueOrDefault(card, 0) + 1;
        }

        List<int> sortedCards = counts.Keys.OrderBy(x => x).ToList();

        foreach (int card in sortedCards) {
            if (counts[card] == 0) continue; // Already used

            for (int i = 0; i < groupSize; i++) {
                int currentCard = card + i;
                if (!counts.ContainsKey(currentCard) || counts[currentCard] == 0) {
                    return false; // Missing card in sequence
                }
                counts[currentCard]--; 
            }
        }

        return true; // Successfully formed groups
    }
}

Complexity

• Time Complexity: O(N log W), where N is the length of the hand and W is the number of unique cards. Sorting the unique cards takes O(W log W) and the iteration takes O(N). In the worst case, W could be close to N, resulting in O(N log N).
• Space Complexity: O(W) due to the dictionary to store card frequencies. In the worst case, W could be close to N.