Problem

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

Given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize, return true if she can rearrange the cards, or false otherwise.

This question is the same as Leetcode 1296: https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/, which states:

Given an array of integers nums and a positive integer k, check whether it is possible to divide this array into sets of k consecutive numbers.

Return true if it is possible. Otherwise, return false.

Examples

Example 1:

Input:
hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output:
 true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]

Example 2:

Input:
hand = [1,2,3,4,5], groupSize = 4
Output:
 false
Explanation: Alice's hand can not be rearranged into groups of 4.

Solution

groupSize is like a fixed-size window W, and we have to find the card in sequence based in all the windows.

Also, second thing is hand size n should be multiple of W. Like in eg. 1, W is 3, and n = 9, so we were able to form 3 groups.

Here is the video explanation:

Method 1 - Using Frequency Hashmap and Greedily Try to Form Groups

  1. Count number of different cards to a map count
  2. Loop from the smallest card number.
  3. Everytime we meet a new card i, we cut off i - i + W - 1 from the counter.

Here we can use treemap, as we need to pick smallest card.

Code

Java
public class Solution {

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

		Map<Integer, Integer> cardCounts = new TreeMap<>();

		for (int card: hand) {
			cardCounts.put(card, cardCounts.getOrDefault(card, 0) + 1);
		}

		// Attempt to form groups starting from the lowest card.
		for (int card: cardCounts.keySet()) {
			int count = cardCounts.get(card);

			if (count > 0) {
				// Check we can form enough groups including card and following groupSize - 1 cards
				for (int i = 1; i < groupSize; i++) {
					int nextCard = card + i;
					int nextCount = cardCounts.getOrDefault(nextCard, 0) - count;

					if (nextCount < 0) {
						return false;
					}

					cardCounts.put(nextCard, nextCount);
				}
			}
		}

		return true;
	}
}
Python
from collections import Counter
from sortedcontainers import SortedDict


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

    # SortedDict will keep the keys sorted just like TreeMap in Java
    cardCounts = SortedDict(Counter(hand))

    while cardCounts:
        # Start with the first (smallest) card
        firstCard = next(iter(cardCounts))
        # Try to pick groupSize consecutive cards starting from firstCard
        for card in range(firstCard, firstCard + groupSize):
            if card not in cardCounts:
                return False
            cardCounts[card] -= 1
            if cardCounts[card] == 0:
                del cardCounts[card]

    return True

Dry Run

First, the hand array is sorted using a TreeMap which also counts the number of occurrences of each card. Here’s the initial cardCounts after sorting and counting:

 Card:   1   2   3   4   6   7   8
 Count:  1   2   2   1   1   1   1

The algorithm will iterate through the cardCounts keys to try and form groups of groupSize = 3.

  • Start with the smallest card 1:
    • cardCounts[1] is 1. We need cards 2 and 3 to complete the group.
    • cardCounts[2] decreases by 1 (from 2 to 1)
    • cardCounts[3] decreases by 1 (from 2 to 1) The group [1,2,3] is formed and we continue.
 Card:   1   2   3   4   6   7   8
 Count:  0   1   1   1   1   1   1
  • Next card is 2:
    • cardCounts[2] is 1. Again, we need cards 3 and 4 to complete the group.
    • cardCounts[3] decreases by 1 (from 1 to 0)
    • cardCounts[4] decreases by 1 (from 1 to 0) The group [2,3,4] is formed and we continue.
 Card:   1   2   3   4   6   7   8
 Count:  0   0   0   0   1   1   1

  • The algorithm skips the card 3 because cardCounts[3] is now 0, which means there’s no more 3 to be used for grouping.

  • The next card with a non-zero count is 6:

    • cardCounts[6] is 1. We try to form a group with cards 6, 7, and 8.
    • cardCounts[7] decreases by 1 (from 1 to 0)
    • cardCounts[8] decreases by 1 (from 1 to 0) The group [6,7,8] is formed and we complete the grouping successfully.
 Card:   1   2   3   4   6   7   8
 Count:  0   0   0   0   0   0   0

The remaining cardCounts are all 0, indicating there are no more cards left and that we’ve successfully grouped all cards without breaking the group-size constraints of 3.

Since we didn’t encounter a situation where we couldn’t form a valid group, the function would return true, indicating that the grouping is indeed possible with the given hand and groupSize.

Complexity

  • ⏰ Time complexity: O(n log n + nw) where n is the number of different cards.
  • 🧺 Space complexity: O(n) for storing values in treemap.

Method 2 - Using MinHeap

In above solution, as groupSize OR W is small, we can loop and look into the hashmap again and again. But what if we are not lucky? groupSize is very large. Then priority queue may help.

Inefficient Code Because of heap.remove

Complexity is O(n^2).

Java
public boolean isNStraightHand(int[] hand, int groupSize) {
	PriorityQueue<Integer> minHeap = new PriorityQueue<>();

	for (int card: hand) {
		minHeap.add(card); // Add cards to the min heap
	}

	while (minHeap.size() != 0) {
		int card = minHeap.poll(); // Get the smallest card
		for (int j = 1; j < groupSize; j++) {
			if (minHeap.remove(card + j)) { // Check if consecutive cards exist
				continue;
			} else {
				return false;
			}
		}
	}

	return true; 
}

Efficient Code with PQ + Hashmap

Java
class Solution {

	public boolean isNStraightHand(int[] hand, int groupSize) {
		int n = hand.length;

		if (n % groupSize != 0) {
			return false;
		}

		Map<Integer, Integer> cardCounts = new HashMap<>();

		for (int card: hand) {
			cardCounts.put(card, cardCounts.getOrDefault(card, 0) + 1);
		}

		PriorityQueue<Integer> minHeap = new PriorityQueue<>(cardCounts.keySet()); 
		while (!minHeap.isEmpty()) {
			int card = minHeap.poll();
			int count = cardCounts.get(card); 
			if (count <= 0) {
				continue; 
			}
			
			for (int i = 1; i < groupSize; i++) { 
				int nextCard = card + i;

				if (!cardCounts.containsKey(nextCard) || cardCounts.get(nextCard) < count) {
					return false;
				} else {
					cardCounts.put(nextCard, cardCounts.get(nextCard) - count); 
				}
			}
		}

		return true; 
	}
}

Dry run

Let’s perform a dry run of the isNStraightHand method with an example hand array and a groupSize. We’ll use the hand array [1,2,3,6,2,3,4,7,8] and groupSize of 3 to walk through the method step-by-step.

First, the hand array is sorted and counts of each card are stored in a TreeMap to ensure the keys (card numbers) are in natural order. Here’s the cardCounts after the loop:

 Card:    1  2  3  4  6  7  8
 Count:   1  2  2  1  1  1  1

A PriorityQueue (minHeap) is initialized with the keys from cardCounts to facilitate ordered access to the smallest card numbers (it serves the same purpose as the iteration over keys in a TreeMap):

 MinHeap: 1  2  3  4  6  7  8

Now, we begin the process of forming groups:

  • Poll 1 from the minHeap:
    • Card count for 1 is 1. This is the start of a new group.
    • Need to check for cards 2 (count should be at least 1) and 3 (count should be at least 1).

The cardCounts after forming group [1,2,3]:

 Card:    1  2  3  4  6  7  8
 Count:   0  1  1  1  1  1  1
  • Poll 2 from the minHeap (since 1’s count is now 0):
    • Card count for 2 is 1. Form a group with 2.
    • Check for cards 3 (count should be at least 1) and 4 (count should be at least 1).

The cardCounts after forming group [1,2,3] and [2,3,4]:

 Card:    1  2  3  4  6  7  8
 Count:   0  0  0  0  1  1  1

  • Poll 3 from the minHeap; however, its count is 0, so continue without doing anything.

  • Poll 4 from the minHeap; its count is 0, so continue.

  • Poll 6 from the minHeap:

    • Card count for 6 is 1. This starts a new group.
    • For a valid group, we need cards 7 (count should be at least 1) and 8 (count should be at least 1).

Now the cardCounts after forming group [1,2,3], [2,3,4], and [6,7,8]:

 Card:    1  2  3  4  6  7  8
 Count:   0  0  0  0  0  0  0
  • All remaining cards in the minHeap have a count of 0, and the method finishes with true.

During the whole process, we didn’t encounter any situation where we were unable to form a group of size groupSize starting with the polled card number. Therefore, the method correctly returns true, indicating it is possible to partition the hand into consecutive groups of the given size.

Complexity

  • ⏰ Time complexity: O(n * log n) - n is number of distinct numbers in hand, but in worst case all the elements
  • 🧺 Space complexity: O(n)