Hand of Straights medium

Problem Statement

You are given an integer array hand representing the cards you hold. You want to check if you can form a group of W consecutive cards. A group consists of W cards of consecutive denominations.

Given an integer W representing the number of consecutive cards in a group, return true if you can form such a group, otherwise return false.

Example 1

Input: hand = [1,2,3,6,2,3,4,7,8], W = 3 Output: true Explanation: We can form two groups of 3 consecutive cards: [1,2,3] and [6,7,8].

Example 2

Input: hand = [1,2,3,4,5], W = 4 Output: false Explanation: We cannot form any group of 4 consecutive cards.

Steps

1. Sort the hand: Sorting the hand allows us to easily identify consecutive cards.
2. Count card frequencies: Use a map to count the frequency of each card.
3. Iterate and check for groups: Iterate through the sorted hand. For each card, check if we can form a group of W consecutive cards starting from that card. If we can, decrement the frequencies of the cards in the group. If we cannot, return false.
4. Return true if all cards are used: If the loop completes without returning false, it means we successfully formed groups for all cards, so we return true.

Explanation

The core idea is to efficiently check for consecutive sequences. Sorting allows for a linear scan. The frequency map avoids redundant counting and allows for quick checks of card availability. The algorithm systematically tries to build groups of size W, ensuring that no card is used more times than it exists. If at any point it's impossible to form a group (because a necessary card is missing or its frequency is insufficient), the function immediately returns false.

Code

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

using namespace std;

bool isNStraightHand(vector<int>& hand, int W) {
    if (hand.size() % W != 0) return false; // Cannot form groups if size is not a multiple of W

    map<int, int> counts;
    for (int card : hand) {
        counts[card]++;
    }

    sort(hand.begin(), hand.end());

    for (int card : hand) {
        if (counts[card] == 0) continue; // Skip already used cards

        for (int i = 0; i < W; ++i) {
            if (counts.find(card + i) == counts.end() || counts[card + i] == 0) {
                return false; // Missing card or insufficient frequency
            }
            counts[card + i]--;
        }
    }

    return true;
}

int main() {
    vector<int> hand1 = {1, 2, 3, 6, 2, 3, 4, 7, 8};
    int W1 = 3;
    cout << "Example 1: " << isNStraightHand(hand1, W1) << endl; // Output: true

    vector<int> hand2 = {1, 2, 3, 4, 5};
    int W2 = 4;
    cout << "Example 2: " << isNStraightHand(hand2, W2) << endl; // Output: false

    return 0;
}

Complexity

• Time Complexity: O(N log N), where N is the number of cards in hand. This is dominated by the sorting step. The map operations (insertion and lookup) have amortized O(1) time complexity.
• Space Complexity: O(N) in the worst case, to store the frequency map. The sorted hand is done in-place for the solution presented, therefore, not adding to space complexity.