Skip to content

1296. Divide Array in Sets of K Consecutive Numbers 👍

  • 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 isPossibleDivide(vector<int>& nums, int k) {
    map<int, int> count;

    for (const int num : nums)
      ++count[num];

    for (const auto& [start, _] : count) {
      const int value = count[start];
      if (value > 0)
        for (int i = start; i < start + k; ++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 isPossibleDivide(int[] nums, int k) {
    TreeMap<Integer, Integer> count = new TreeMap<>();

    for (final int num : nums)
      count.merge(num, 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 + k; ++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 isPossibleDivide(self, nums: list[int], k: int) -> bool:
    count = collections.Counter(nums)

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

    return True