Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

846. Hand of Straights

Time: $O(m\log m + mk)$, where $m$ = # of different nums

Space: $O(m)$

			


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;
  }
};




			


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;
  }
}




			


class Solution:
  def isNStraightHand(self, hand: List[int], W: int) -> bool:
    count = 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