Skip to content

846. Hand of Straights 👍

  • Time: $O(m\log m + mk)$, where $m$ = # of different nums
  • Space: $O(m)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  bool isNStraightHand(vector<int>& hand, int groupSize) {
    map<int, int> count;

    for (const int card : hand)
      ++count[card];

    for (const auto& [start, _] : count) {
      const int value = count[start];
      if (value > 0)
        for (int i = start; i < start + groupSize; ++i) {
          count[i] -= value;
          if (count[i] < 0)
            return false;
        }
    }

    return true;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public boolean isNStraightHand(int[] hand, int groupSize) {
    TreeMap<Integer, Integer> count = new TreeMap<>();

    for (final int card : hand)
      count.merge(card, 1, Integer::sum);

    for (final int start : count.keySet()) {
      final int value = count.getOrDefault(start, 0);
      if (value > 0)
        for (int i = start; i < start + groupSize; ++i)
          if (count.merge(i, -value, Integer::sum) < 0)
            return false;
    }

    return true;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def isNStraightHand(self, hand: list[int], groupSize: int) -> bool:
    count = collections.Counter(hand)

    for start in sorted(count):
      value = count[start]
      if value > 0:
        for i in range(start, start + groupSize):
          count[i] -= value
          if count[i] < 0:
            return False

    return True