Welcome to Subscribe On Youtube
846. Hand of Straights
Description
Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards.
Given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize, return true if she can rearrange the cards, or false otherwise.
Example 1:
Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3 Output: true Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]
Example 2:
Input: hand = [1,2,3,4,5], groupSize = 4 Output: false Explanation: Alice's hand can not be rearranged into groups of 4.
Constraints:
1 <= hand.length <= 1040 <= hand[i] <= 1091 <= groupSize <= hand.length
Note: This question is the same as 1296: https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/
Solutions
-
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; } } -
class Solution { public: bool isNStraightHand(vector<int>& hand, int groupSize) { unordered_map<int, int> cnt; for (int& v : hand) ++cnt[v]; sort(hand.begin(), hand.end()); for (int& v : hand) { if (cnt.count(v)) { for (int x = v; x < v + groupSize; ++x) { if (!cnt.count(x)) { return false; } if (--cnt[x] == 0) { cnt.erase(x); } } } } 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 -
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 } -
function isNStraightHand(hand: number[], groupSize: number) { const cnt: Record<number, number> = {}; for (const i of hand) { cnt[i] = (cnt[i] ?? 0) + 1; } const keys = Object.keys(cnt).map(Number); for (const i of keys) { while (cnt[i]) { for (let j = i; j < groupSize + i; j++) { if (!cnt[j]) { return false; } cnt[j]--; } } } return true; } -
class Solution { public boolean isNStraightHand(int[] hand, int groupSize) { if (hand.length % groupSize != 0) { return false; } TreeMap<Integer, Integer> tm = new TreeMap<>(); for (int x : hand) { tm.merge(x, 1, Integer::sum); } while (!tm.isEmpty()) { int x = tm.firstKey(); for (int y = x; y < x + groupSize; ++y) { int t = tm.merge(y, -1, Integer::sum); if (t < 0) { return false; } if (t == 0) { tm.remove(y); } } } return true; } } -
class Solution { public: bool isNStraightHand(vector<int>& hand, int groupSize) { if (hand.size() % groupSize) { return false; } map<int, int> mp; for (int x : hand) { ++mp[x]; } while (!mp.empty()) { int x = mp.begin()->first; for (int y = x; y < x + groupSize; ++y) { if (!mp.contains(y)) { return false; } if (--mp[y] == 0) { mp.erase(y); } } } return true; } }; -
class Solution: def isNStraightHand(self, hand: List[int], groupSize: int) -> bool: if len(hand) % groupSize: return False cnt = Counter(hand) sd = SortedDict(cnt) while sd: x = next(iter(sd)) for y in range(x, x + groupSize): if y not in sd: return False if sd[y] == 1: del sd[y] else: sd[y] -= 1 return True -
func isNStraightHand(hand []int, groupSize int) bool { if len(hand)%groupSize != 0 { return false } tm := treemap.NewWithIntComparator() for _, x := range hand { if v, ok := tm.Get(x); ok { tm.Put(x, v.(int)+1) } else { tm.Put(x, 1) } } for !tm.Empty() { x, _ := tm.Min() for y := x.(int); y < x.(int)+groupSize; y++ { if v, ok := tm.Get(y); ok { if v.(int) == 1 { tm.Remove(y) } else { tm.Put(y, v.(int)-1) } } else { return false } } } return true } -
function isNStraightHand(hand: number[], groupSize: number): boolean { if (hand.length % groupSize !== 0) { return false; } const tm = new TreeMap<number, number>(); for (const x of hand) { tm.set(x, (tm.get(x) || 0) + 1); } while (tm.size()) { const x = tm.first()![0]; for (let y = x; y < x + groupSize; ++y) { if (!tm.has(y)) { return false; } if (tm.get(y)! === 1) { tm.delete(y); } else { tm.set(y, tm.get(y)! - 1); } } } return true; } type Compare<T> = (lhs: T, rhs: T) => number; class RBTreeNode<T = number> { data: T; count: number; left: RBTreeNode<T> | null; right: RBTreeNode<T> | null; parent: RBTreeNode<T> | null; color: number; constructor(data: T) { this.data = data; this.left = this.right = this.parent = null; this.color = 0; this.count = 1; } sibling(): RBTreeNode<T> | null { if (!this.parent) return null; // sibling null if no parent return this.isOnLeft() ? this.parent.right : this.parent.left; } isOnLeft(): boolean { return this === this.parent!.left; } hasRedChild(): boolean { return ( Boolean(this.left && this.left.color === 0) || Boolean(this.right && this.right.color === 0) ); } } class RBTree<T> { root: RBTreeNode<T> | null; lt: (l: T, r: T) => boolean; constructor(compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0)) { this.root = null; this.lt = (l: T, r: T) => compare(l, r) < 0; } rotateLeft(pt: RBTreeNode<T>): void { const right = pt.right!; pt.right = right.left; if (pt.right) pt.right.parent = pt; right.parent = pt.parent; if (!pt.parent) this.root = right; else if (pt === pt.parent.left) pt.parent.left = right; else pt.parent.right = right; right.left = pt; pt.parent = right; } rotateRight(pt: RBTreeNode<T>): void { const left = pt.left!; pt.left = left.right; if (pt.left) pt.left.parent = pt; left.parent = pt.parent; if (!pt.parent) this.root = left; else if (pt === pt.parent.left) pt.parent.left = left; else pt.parent.right = left; left.right = pt; pt.parent = left; } swapColor(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void { const tmp = p1.color; p1.color = p2.color; p2.color = tmp; } swapData(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void { const tmp = p1.data; p1.data = p2.data; p2.data = tmp; } fixAfterInsert(pt: RBTreeNode<T>): void { let parent = null; let grandParent = null; while (pt !== this.root && pt.color !== 1 && pt.parent?.color === 0) { parent = pt.parent; grandParent = pt.parent.parent; /* Case : A Parent of pt is left child of Grand-parent of pt */ if (parent === grandParent?.left) { const uncle = grandParent.right; /* Case : 1 The uncle of pt is also red Only Recoloring required */ if (uncle && uncle.color === 0) { grandParent.color = 0; parent.color = 1; uncle.color = 1; pt = grandParent; } else { /* Case : 2 pt is right child of its parent Left-rotation required */ if (pt === parent.right) { this.rotateLeft(parent); pt = parent; parent = pt.parent; } /* Case : 3 pt is left child of its parent Right-rotation required */ this.rotateRight(grandParent); this.swapColor(parent!, grandParent); pt = parent!; } } else { /* Case : B Parent of pt is right child of Grand-parent of pt */ const uncle = grandParent!.left; /* Case : 1 The uncle of pt is also red Only Recoloring required */ if (uncle != null && uncle.color === 0) { grandParent!.color = 0; parent.color = 1; uncle.color = 1; pt = grandParent!; } else { /* Case : 2 pt is left child of its parent Right-rotation required */ if (pt === parent.left) { this.rotateRight(parent); pt = parent; parent = pt.parent; } /* Case : 3 pt is right child of its parent Left-rotation required */ this.rotateLeft(grandParent!); this.swapColor(parent!, grandParent!); pt = parent!; } } } this.root!.color = 1; } delete(val: T): boolean { const node = this.find(val); if (!node) return false; node.count--; if (!node.count) this.deleteNode(node); return true; } deleteAll(val: T): boolean { const node = this.find(val); if (!node) return false; this.deleteNode(node); return true; } deleteNode(v: RBTreeNode<T>): void { const u = BSTreplace(v); // True when u and v are both black const uvBlack = (u === null || u.color === 1) && v.color === 1; const parent = v.parent!; if (!u) { // u is null therefore v is leaf if (v === this.root) this.root = null; // v is root, making root null else { if (uvBlack) { // u and v both black // v is leaf, fix double black at v this.fixDoubleBlack(v); } else { // u or v is red if (v.sibling()) { // sibling is not null, make it red" v.sibling()!.color = 0; } } // delete v from the tree if (v.isOnLeft()) parent.left = null; else parent.right = null; } return; } if (!v.left || !v.right) { // v has 1 child if (v === this.root) { // v is root, assign the value of u to v, and delete u v.data = u.data; v.left = v.right = null; } else { // Detach v from tree and move u up if (v.isOnLeft()) parent.left = u; else parent.right = u; u.parent = parent; if (uvBlack) this.fixDoubleBlack(u); // u and v both black, fix double black at u else u.color = 1; // u or v red, color u black } return; } // v has 2 children, swap data with successor and recurse this.swapData(u, v); this.deleteNode(u); // find node that replaces a deleted node in BST function BSTreplace(x: RBTreeNode<T>): RBTreeNode<T> | null { // when node have 2 children if (x.left && x.right) return successor(x.right); // when leaf if (!x.left && !x.right) return null; // when single child return x.left ?? x.right; } // find node that do not have a left child // in the subtree of the given node function successor(x: RBTreeNode<T>): RBTreeNode<T> { let temp = x; while (temp.left) temp = temp.left; return temp; } } fixDoubleBlack(x: RBTreeNode<T>): void { if (x === this.root) return; // Reached root const sibling = x.sibling(); const parent = x.parent!; if (!sibling) { // No sibiling, double black pushed up this.fixDoubleBlack(parent); } else { if (sibling.color === 0) { // Sibling red parent.color = 0; sibling.color = 1; if (sibling.isOnLeft()) this.rotateRight(parent); // left case else this.rotateLeft(parent); // right case this.fixDoubleBlack(x); } else { // Sibling black if (sibling.hasRedChild()) { // at least 1 red children if (sibling.left && sibling.left.color === 0) { if (sibling.isOnLeft()) { // left left sibling.left.color = sibling.color; sibling.color = parent.color; this.rotateRight(parent); } else { // right left sibling.left.color = parent.color; this.rotateRight(sibling); this.rotateLeft(parent); } } else { if (sibling.isOnLeft()) { // left right sibling.right!.color = parent.color; this.rotateLeft(sibling); this.rotateRight(parent); } else { // right right sibling.right!.color = sibling.color; sibling.color = parent.color; this.rotateLeft(parent); } } parent.color = 1; } else { // 2 black children sibling.color = 0; if (parent.color === 1) this.fixDoubleBlack(parent); else parent.color = 1; } } } } insert(data: T): boolean { // search for a position to insert let parent = this.root; while (parent) { if (this.lt(data, parent.data)) { if (!parent.left) break; else parent = parent.left; } else if (this.lt(parent.data, data)) { if (!parent.right) break; else parent = parent.right; } else break; } // insert node into parent const node = new RBTreeNode(data); if (!parent) this.root = node; else if (this.lt(node.data, parent.data)) parent.left = node; else if (this.lt(parent.data, node.data)) parent.right = node; else { parent.count++; return false; } node.parent = parent; this.fixAfterInsert(node); return true; } search(predicate: (val: T) => boolean, direction: 'left' | 'right'): T | undefined { let p = this.root; let result = null; while (p) { if (predicate(p.data)) { result = p; p = p[direction]; } else { p = p[direction === 'left' ? 'right' : 'left']; } } return result?.data; } find(data: T): RBTreeNode<T> | null { let p = this.root; while (p) { if (this.lt(data, p.data)) { p = p.left; } else if (this.lt(p.data, data)) { p = p.right; } else break; } return p ?? null; } count(data: T): number { const node = this.find(data); return node ? node.count : 0; } *inOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> { if (!root) return; for (const v of this.inOrder(root.left!)) yield v; yield root.data; for (const v of this.inOrder(root.right!)) yield v; } *reverseInOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> { if (!root) return; for (const v of this.reverseInOrder(root.right!)) yield v; yield root.data; for (const v of this.reverseInOrder(root.left!)) yield v; } } class TreeMap<K = number, V = unknown> { _size: number; tree: RBTree<K>; map: Map<K, V> = new Map(); compare: Compare<K>; constructor( collection: Array<[K, V]> | Compare<K> = [], compare: Compare<K> = (l: K, r: K) => (l < r ? -1 : l > r ? 1 : 0), ) { if (typeof collection === 'function') { compare = collection; collection = []; } this._size = 0; this.compare = compare; this.tree = new RBTree(compare); for (const [key, val] of collection) this.set(key, val); } size(): number { return this._size; } has(key: K): boolean { return !!this.tree.find(key); } get(key: K): V | undefined { return this.map.get(key); } set(key: K, val: V): boolean { const successful = this.tree.insert(key); this._size += successful ? 1 : 0; this.map.set(key, val); return successful; } delete(key: K): boolean { const deleted = this.tree.deleteAll(key); this._size -= deleted ? 1 : 0; return deleted; } ceil(target: K): [K, V] | undefined { return this.toKeyValue(this.tree.search(key => this.compare(key, target) >= 0, 'left')); } floor(target: K): [K, V] | undefined { return this.toKeyValue(this.tree.search(key => this.compare(key, target) <= 0, 'right')); } higher(target: K): [K, V] | undefined { return this.toKeyValue(this.tree.search(key => this.compare(key, target) > 0, 'left')); } lower(target: K): [K, V] | undefined { return this.toKeyValue(this.tree.search(key => this.compare(key, target) < 0, 'right')); } first(): [K, V] | undefined { return this.toKeyValue(this.tree.inOrder().next().value); } last(): [K, V] | undefined { return this.toKeyValue(this.tree.reverseInOrder().next().value); } shift(): [K, V] | undefined { const first = this.first(); if (first === undefined) return undefined; this.delete(first[0]); return first; } pop(): [K, V] | undefined { const last = this.last(); if (last === undefined) return undefined; this.delete(last[0]); return last; } toKeyValue(key: K): [K, V]; toKeyValue(key: undefined): undefined; toKeyValue(key: K | undefined): [K, V] | undefined; toKeyValue(key: K | undefined): [K, V] | undefined { return key != null ? [key, this.map.get(key)!] : undefined; } *[Symbol.iterator](): Generator<[K, V], void, void> { for (const key of this.keys()) yield this.toKeyValue(key); } *keys(): Generator<K, void, void> { for (const key of this.tree.inOrder()) yield key; } *values(): Generator<V, undefined, void> { for (const key of this.keys()) yield this.map.get(key)!; return undefined; } *rkeys(): Generator<K, undefined, void> { for (const key of this.tree.reverseInOrder()) yield key; return undefined; } *rvalues(): Generator<V, undefined, void> { for (const key of this.rkeys()) yield this.map.get(key)!; return undefined; } }