Hand of Straights

January 10, 2025

Hand of Straights: Checking Consecutive Card Groups

The Hand of Straights problem involves rearranging cards into groups of a specified size such that the card values in each group are consecutive.

This problem challenges us to implement an efficient algorithm to determine if such a rearrangement is possible.

Problem Description

Given:

An integer array hand, where hand[i] is the value of the $i^{th}$ card.
An integer groupSize, representing the required size of each group.

Goal

Determine if it is possible to divide all cards into groups of size groupSize, where the card values in each group are consecutive. Return true if possible, otherwise false.

Example 1

Input: hand = [1,2,4,2,3,5,3,4], groupSize = 4

Output: true

Explanation:
The cards can be rearranged as [1,2,3,4] and [2,3,4,5].

Example 2

Input: hand = [1,2,3,3,4,5,6,7], groupSize = 4

Output: false

Explanation: The closest we can get is [1,2,3,4] and [3,5,6,7], but the cards in the second group are not consecutive.

Approach

Key Insights

Grouping by Size:
- To divide all cards into groups of size the total number of cards () must be divisible by
Using a Frequency Map:
- Count the occurrences of each card using a frequency map (or dictionary).
- Always start forming groups from the smallest card value available to ensure proper sequencing.
Forming Consecutive Groups:
- For each card, if it is the starting card of a new group:
  - Ensure the next $k - 1$ consecutive cards exist.
  - Decrease their counts in the frequency map.
Invalid Cases:
- If any card count is too low to start a group, return false.

Algorithm

Precheck:
- If $\mod k \neq 0$ , immediately return false.
Frequency Map:
- Create a frequency map to track the count of each card in hand.
Iterate Over Cards:
- Sort the card values.
- For each card, attempt to form a group starting with that card.
- If any card cannot form a valid group, return false.
Return Result:
- If all cards are successfully grouped, return true.

There are mainly Four approach to solve this problem –

Brute Force
Sweep Line Algorithm
Min Heap
Min Segment Tree (Lazy Propagation)

1. Sorting

Time complexity: O(nlogn)
Space complexity: O(n)

Python

C++

Java

JavaScript

Python

class Solution:
    def isNStraightHand(self, hand, groupSize):
        if len(hand) % groupSize:
            return False
        count = Counter(hand)
        hand.sort()
        for num in hand:
            if count[num]:
                for i in range(num, num + groupSize):
                    if not count[i]:
                        return False
                    count[i] -= 1
        return True

C++

class Solution {
public:
    bool isNStraightHand(vector& hand, int groupSize) {
        if (hand.size() % groupSize != 0) return false;
        unordered_map count;
        for (int num : hand) count[num]++;
        sort(hand.begin(), hand.end());
        for (int num : hand) {
            if (count[num] > 0) {
                for (int i = num; i < num + groupSize; i++) {
                    if (count[i] == 0) return false;
                    count[i]--;
                }
            }
        }
        return true;
    }
};

Java

public class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0) return false;
        Map count = new HashMap<>();
        for (int num : hand) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        Arrays.sort(hand);
        for (int num : hand) {
            if (count.get(num) > 0) {
                for (int i = num; i < num + groupSize; i++) {
                    if (count.getOrDefault(i, 0) == 0) return false;
                    count.put(i, count.get(i) - 1);
                }
            }
        }
        return true;
    }
}

JavaScript

class Solution {
    /**
     * @param {number[]} hand
     * @param {number} groupSize
     * @return {boolean}
     */
    isNStraightHand(hand, groupSize) {
        if (hand.length % groupSize !== 0) {
            return false;
        }
        const count = {};
        for (const num of hand) {
            count[num] = (count[num] || 0) + 1;
        }
        hand.sort((a, b) => a - b);
        for (const num of hand) {
            if (count[num] > 0) {
                for (let i = num; i < num + groupSize; i++) {
                    if (!count[i]) return false;
                    count[i] -= 1;
                }
            }
        }
        return true;
    }
}

2. Heap

Time & Space Complexity

Time complexity: $O (n log n)$
Space complexity:

C++

Java

Python

JavaScript

C++

class Solution {
public:
    bool isNStraightHand(vector& hand, int groupSize) {
        if (hand.size() % groupSize != 0)
            return false;

        unordered_map count;
        for (int n : hand)
            count[n] = 1 + count[n];

        priority_queue, greater> minH;
        for (auto& pair : count)
            minH.push(pair.first);

        while (!minH.empty()) {
            int first = minH.top();
            for (int i = first; i < first + groupSize; i++) {
                if (count.find(i) == count.end())
                    return false;
                count[i] -= 1;
                if (count[i] == 0) {
                    if (i != minH.top())
                        return false;
                    minH.pop();
                }
            }
        }
        return true;
    }
};

Java

public class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0)
            return false;

        Map count = new HashMap<>();
        for (int n : hand)
            count.put(n, 1 + count.getOrDefault(n, 0));

        PriorityQueue minH = new PriorityQueue<>(count.keySet());
        while (!minH.isEmpty()) {
            int first = minH.peek();
            for (int i = first; i < first + groupSize; i++) {
                if (!count.containsKey(i))
                    return false;
                count.put(i, count.get(i) - 1);
                if (count.get(i) == 0) {
                    if (i != minH.peek())
                        return false;
                    minH.poll();
                }
            }
        }
        return true;
    }
}

Python

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize:
            return False

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

        minH = list(count.keys())
        heapq.heapify(minH)
        while minH:
            first = minH[0]
            for i in range(first, first + groupSize):
                if i not in count:
                    return False
                count[i] -= 1
                if count[i] == 0:
                    if i != minH[0]:
                        return False
                    heapq.heappop(minH)
        return True

JavaScript

class Solution {
    /**
     * @param {string} num1
     * @param {string} num2
     * @return {string}
     */
    multiply(num1, num2) {
        if (num1 === '0' || num2 === '0') {
            return '0';
        }

        const res = new Array(num1.length + num2.length).fill(0);
        num1 = num1.split('').reverse().join('');
        num2 = num2.split('').reverse().join('');
        for (let i1 = 0; i1 < num1.length; i1++) {
            for (let i2 = 0; i2 < num2.length; i2++) {
                const digit = parseInt(num1[i1]) * parseInt(num2[i2]);
                res[i1 + i2] += digit;
                res[i1 + i2 + 1] += Math.floor(res[i1 + i2] / 10);
                res[i1 + i2] %= 10;
            }
        }

        let result = '';
        let i = res.length - 1;
        while (i >= 0 && res[i] === 0) {
            i--;
        }
        while (i >= 0) {
            result += res[i--];
        }
        return result;
    }
}

3. Ordered Map

Time & Space Complexity

Time complexity: $n log n)$
Space complexity:

C++

Java

Python

JavaScript

C++

class Solution {
public:
    bool isNStraightHand(vector& hand, int groupSize) {
        if (hand.size() % groupSize != 0) return false;

        map count;
        for (int num : hand) count[num]++;
        
        queue q;
        int lastNum = -1, openGroups = 0;

        for (auto& entry : count) {
            int num = entry.first;
            if ((openGroups > 0 && num > lastNum + 1) || 
                 openGroups > count[num]) {
                return false;
            }

            q.push(count[num] - openGroups);
            lastNum = num;
            openGroups = count[num];

            if (q.size() == groupSize) {
                openGroups -= q.front();
                q.pop();
            }
        }
        return openGroups == 0;
    }
};

Java

public class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0) return false;

        Map count = new TreeMap<>();
        for (int num : hand) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        Queue q = new LinkedList<>();
        int lastNum = -1, openGroups = 0;

        for (int num : count.keySet()) {
            if ((openGroups > 0 && num > lastNum + 1) || 
                 openGroups > count.get(num)) {
                return false;
            }

            q.add(count.get(num) - openGroups);
            lastNum = num;
            openGroups = count.get(num);

            if (q.size() == groupSize) {
                openGroups -= q.poll();
            }
        }
        return openGroups == 0;
    }
}

Python

class Solution:
    def isNStraightHand(self, hand, groupSize):
        if len(hand) % groupSize != 0:
            return False

        count = Counter(hand)
        q = deque()
        last_num, open_groups = -1, 0

        for num in sorted(count):
            if ((open_groups > 0 and num > last_num + 1) or 
                open_groups > count[num]
            ):
                return False

            q.append(count[num] - open_groups)
            last_num = num
            open_groups = count[num]

            if len(q) == groupSize:
                open_groups -= q.popleft()

        return open_groups == 0

JavaScript

class Solution {
    /**
     * @param {number[]} hand
     * @param {number} groupSize
     * @return {boolean}
     */
    isNStraightHand(hand, groupSize) {
        if (hand.length % groupSize !== 0) return false;

        let count = new Map();
        hand.forEach(num => count.set(num, (count.get(num) || 0) + 1));

        let q = new Queue();
        let lastNum = -1, openGroups = 0;

        Array.from(count.keys()).sort((a, b) => a - b).forEach(num => {
            if ((openGroups > 0 && num > lastNum + 1) || 
                 openGroups > count.get(num)) {
                return false;
            }

            q.push(count.get(num) - openGroups);
            lastNum = num;
            openGroups = count.get(num);

            if (q.size() === groupSize) {
                openGroups -= q.pop();
            }
        });

        return openGroups === 0;
    }
}

Unlock this article for Free,
by logging in

Hand of Straights

Hand of Straights: Checking Consecutive Card Groups

Problem Description

Goal

Approach

Key Insights

Algorithm

There are mainly Four approach to solve this problem –

1. Sorting

2. Heap

Time & Space Complexity

3. Ordered Map

Time & Space Complexity

More Articles

30+ Companies are Hiring

Unlock this article for Free, by logging in

Hand of Straights

Hand of Straights: Checking Consecutive Card Groups

Problem Description

Goal

Approach

Key Insights

Algorithm

There are mainly Four approach to solve this problem –

1. Sorting

2. Heap

Time & Space Complexity

3. Ordered Map

Time & Space Complexity

More Articles

30+ Companies are Hiring

Unlock this article for Free,
by logging in