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's hand can 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's hand can't be rearranged into groups of 4.

 

Constraints:

  • 1 <= hand.length <= 10000
  • 0 <= hand[i] <= 10^9
  • 1 <= 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
    }
    

All Problems

All Solutions