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 True
This 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 <stdio.h>
2#
This C implementation uses sorting and a simple array to keep track of card counts, applying the greedy grouping in a straightforward manner.