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 W) {
    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 + W; ++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
19
20
class Solution {
  public boolean isNStraightHand(int[] hand, int W) {
    TreeMap<Integer, Integer> count = new TreeMap<>();

    for (final int card : hand)
      count.put(card, count.getOrDefault(card, 0) + 1);

    for (final int start : count.keySet()) {
      final int value = count.getOrDefault(start, 0);
      if (value > 0)
        for (int i = start; i < start + W; ++i) {
          count.put(i, count.getOrDefault(i, 0) - value);
          if (count.get(i) < 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], W: int) -> bool:
    count = collections.Counter(hand)

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

    return True