846.Hand_of_Straights(Medium).md

846. Hand of Straights (Medium)

Date and Time: Aug 17, 2024, 20:19 (EST)

Link: https://leetcode.com/problems/hand-of-straights/

Question:

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.

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.

Constraints:

• 1 <= hand.length <= 10^4

• 0 <= hand[i] <= 10^9

• 1 <= groupSize <= hand.length

Walk-through:

1. The base case if len(hand) % groupSize != 0, we know hand cannot be rearrange into group of size groupSize.

2. We store each element from hand into a hashmap count.

3. Create a minHeap to store the keys of count{}.

4. We loop over minHeap from first = minHeap[0] to [first, first + groupSize]. If i between [first, first + groupSize] is not in count, we return False. Then we decrement count[i] -= 1, and check if count[i] == 0, if yes, we check if count[i] != minHeap[0] because we only want to pop the first (smallest) element from the minHeap by heapq.heappop(minHeap), otherwise, we should return False.

Python Solution:

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        # Check if we can split hand evenly into groupSize
        if len(hand) % groupSize != 0:
            return False
        count = {}
        for i in hand:
            count[i] = count.get(i, 0) + 1
        minHeap = list(count.keys())
        heapq.heapify(minHeap)
        while minHeap:
            first = minHeap[0]
            for i in range(first, first + groupSize):
                # Check if group is consecutive
                if i not in count:
                    return False
                count[i] -= 1
                if count[i] == 0:
                    # Check if elements instead of min in minHeap is 0 in count
                    # If non min is 0 in count that means we will not have consecutive in next group
                    if i != minHeap[0]:
                        return False
                    heapq.heappop(minHeap)
        return True

Time Complexity: $O(nlog\ n)$, n is len(hand), because for each element in hand we need to pop first from minHeap,which takes log n time compleixty.
Space Complexity: $O(n)$

Java Solution:

We create minHeap by passing count.keySet to PriorityQueue, which will avoid having duplicate keys. peek() will allow us to get the first element, poll() will remove the first element.

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0) {
            return false;
        }
        Map<Integer, Integer> count = new HashMap<>();
        for (int i: hand) {
            count.put(i, count.getOrDefault(i, 0) + 1);
        }
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(count.keySet());
        while (!minHeap.isEmpty()) {
            int first = minHeap.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 != minHeap.peek()) {
                        return false;
                    }
                    minHeap.poll();
                }
            }
        }
        return true;
    }
}

C++ Solution:

map.begin() gets an iterator to the first element in the map. map.begin()->first gets the first element in the map.
count.end() points pass the last element in count, so it compares if count[i] doesn't exist.

class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int groupSize) {
        if (hand.size() % groupSize != 0) {
            return false;
        }
        unordered_map<int, int> count;
        for (int card : hand) {
            count[card]++;
        }
        priority_queue<int, vector<int>, greater<int>> minHeap;
        for (const auto& entry : count) {
            minHeap.push(entry.first);
        }
        while (!minHeap.empty()) {
            int first = minHeap.top();
            for (int i = first; i < first + groupSize; i++) {
                if (count.find(i) == count.end()) {
                    return false;
                }
                count[i]--;
                if (count[i] == 0) {
                    if (i != minHeap.top()) {
                        return false;
                    }
                    minHeap.pop();
                }
            }
        }
        return true;
    }
};

Runtime and Memory comparison

Language	Runtime	Memory
Python3	154 ms	18.6 MB
Java	34 ms	46.1 MB
C++	38 ms	32.4 MB