846

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/
// Author: github.com/lzl124631x
// 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/
// Author: github.com/lzl124631x
// 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/
// Author: github.com/lzl124631x
// 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;
    }
};