Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/846.html
846. Hand of Straights (Medium)
Alice has a hand of cards, given as an array of integers.
Now she wants to rearrange the cards into groups so that each group is size W, and consists of W consecutive cards.
Return true if and only if she can.
Example 1:
Input: hand = [1,2,3,6,2,3,4,7,8], W = 3 Output: true Explanation: Alice'shandcan be rearranged as[1,2,3],[2,3,4],[6,7,8].
Example 2:
Input: hand = [1,2,3,4,5], W = 4 Output: false Explanation: Alice'shandcan't be rearranged into groups of4.
Constraints:
1 <= hand.length <= 100000 <= hand[i] <= 10^91 <= W <= hand.length
Note: This question is the same as 1296: https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/
Related Topics:
Ordered Map
Solution 1. Multiset
// OJ: https://leetcode.com/problems/hand-of-straights/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
bool isNStraightHand(vector<int>& A, int W) {
multiset<int> s(begin(A), end(A));
while (s.size()) {
int n = *s.begin();
s.erase(s.begin());
for (int i = 1; i < W; ++i) {
auto it = s.find(n + i);
if (it == s.end()) return false;
s.erase(it);
}
}
return true;
}
};
Solution 2. Map
// OJ: https://leetcode.com/problems/hand-of-straights/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
bool isNStraightHand(vector<int>& A, int W) {
map<int, int> m;
for (int n : A) m[n]++;
while (m.size()) {
int n = m.begin()->first;
if (--m[n] == 0) m.erase(n);
for (int i = 1; i < W; ++i) {
if (m.count(n + i) == 0) return false;
if (--m[n + i] == 0) m.erase(n + i);
}
}
return true;
}
};
One optimization is that we can delete multiple group at the same time.
// OJ: https://leetcode.com/problems/hand-of-straights/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
bool isNStraightHand(vector<int>& A, int W) {
map<int, int> m;
for (int n : A) m[n]++;
while (m.size()) {
int n = m.begin()->first, cnt = m.begin()->second;
m.erase(n);
for (int i = 1; i < W; ++i) {
if (m[n + i] < cnt) return false;
if ((m[n + i] -= cnt) == 0) m.erase(n + i);
}
}
return true;
}
};
-
class Solution { public boolean isNStraightHand(int[] hand, int W) { if (hand == null || hand.length == 0) return false; int length = hand.length; if (length % W != 0) return false; TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>(); for (int num : hand) { int count = map.getOrDefault(num, 0) + 1; map.put(num, count); } while (map.size() > 0) { int start = map.firstKey(); int end = start + W - 1; for (int i = start; i <= end; i++) { int count = map.getOrDefault(i, 0); if (count == 0) return false; count--; if (count == 0) map.remove(i); else map.put(i, count); } } return true; } } ############ class Solution { public boolean isNStraightHand(int[] hand, int groupSize) { Map<Integer, Integer> cnt = new HashMap<>(); for (int v : hand) { cnt.put(v, cnt.getOrDefault(v, 0) + 1); } Arrays.sort(hand); for (int v : hand) { if (cnt.containsKey(v)) { for (int x = v; x < v + groupSize; ++x) { if (!cnt.containsKey(x)) { return false; } cnt.put(x, cnt.get(x) - 1); if (cnt.get(x) == 0) { cnt.remove(x); } } } } return true; } } -
// OJ: https://leetcode.com/problems/hand-of-straights/ // Time: O(NlogN) // Space: O(N) class Solution { public: bool isNStraightHand(vector<int>& A, int W) { multiset<int> s(begin(A), end(A)); while (s.size()) { int n = *s.begin(); s.erase(s.begin()); for (int i = 1; i < W; ++i) { auto it = s.find(n + i); if (it == s.end()) return false; s.erase(it); } } return true; } }; -
class Solution: def isNStraightHand(self, hand: List[int], groupSize: int) -> bool: cnt = Counter(hand) for v in sorted(hand): if cnt[v]: for x in range(v, v + groupSize): if cnt[x] == 0: return False cnt[x] -= 1 if cnt[x] == 0: cnt.pop(x) return True ############ class Solution(object): def isNStraightHand(self, hand, W): """ :type hand: List[int] :type W: int :rtype: bool """ cards = collections.Counter(hand) while cards: start = min(cards.keys()) start_val = cards[start] for card in range(start, start + W): if card not in cards: return False cards[card] -= start_val if cards[card] == 0: cards.pop(card) elif cards[card] < 0: return False return not cards -
func isNStraightHand(hand []int, groupSize int) bool { cnt := map[int]int{} for _, v := range hand { cnt[v]++ } sort.Ints(hand) for _, v := range hand { if _, ok := cnt[v]; ok { for x := v; x < v+groupSize; x++ { if _, ok := cnt[x]; !ok { return false } cnt[x]-- if cnt[x] == 0 { delete(cnt, x) } } } } return true }