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 <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.