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.
1from collections import Counter
2
3def isPossibleDivide(hand, groupSize):
4 if len(hand) % groupSize != 0:
5 return False
6 hand_count = Counter(hand)
7 for card in sorted(hand_count):
8 if hand_count[card] > 0:
9 for i in range(groupSize):
10 if hand_count[card + i] < hand_count[card]:
11 return False
12 hand_count[card + i] -= hand_count[card]
13 return TrueThis Python code first uses a Counter to count occurrences of each card. It then attempts to form groups starting from the smallest card available, reducing counts appropriately.
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.