Sponsored
Sponsored
We can sort the array first and then use a greedy approach to construct consecutive groups of the given group size:
Time Complexity: O(N log N) due to sorting, where N is the number of cards. Space Complexity: O(N) for storing the counts.
1import java.util.*;
2
3public class HandOfStraights {
4 public boolean isPossibleDivide(int[] hand, int groupSize) {
5 if (hand.length % groupSize != 0) return false;
6 Map<Integer, Integer> count = new HashMap<>();
7 for (int card : hand) {
8 count.put(card, count.getOrDefault(card, 0) + 1);
9 }
10 PriorityQueue<Integer> minHeap = new PriorityQueue<>(count.keySet());
11 while (!minHeap.isEmpty()) {
12 int first = minHeap.poll();
13 for (int i = 0; i < groupSize; i++) {
14 if (count.getOrDefault(first + i, 0) == 0) return false;
15 count.put(first + i, count.get(first + i) - 1);
16 if (count.get(first + i) == 0) {
17 count.remove(first + i);
18 }
19 }
20 }
21 return true;
22 }
23}This Java code uses a HashMap to store counts and a PriorityQueue (min-heap) to process cards in sorted order, attempting to form groups from smallest to largest.
This approach uses a multiset (or similar structure) to represent the occurrence of each card. It uses a similar greedy process as Approach 1 but leverages enhanced data structures for efficient access:
Time Complexity: O(N log N) due to map operations. Space Complexity: O(N) for the map to store counts.
1#include <vector>
2#include <map>
3using namespace std;
4
5class Solution {
public:
bool isPossibleDivide(vector<int>& hand, int groupSize) {
map<int, int> count;
for (int card : hand) {
count[card]++;
}
for (auto it = count.begin(); it != count.end(); ++it) {
int card = it->first;
int freq = it->second;
if (freq > 0) {
for (int i = 0; i < groupSize; i++) {
if (count[card + i] < freq) return false;
count[card + i] -= freq;
}
}
}
return true;
}
};This C++ solution uses a map (similar to a multiset here) to maintain count of each card and iterates with greedy logic to form groups by decreasing the count of cards as it goes.