[Leetcode] Problem 1296 - Divide Array in Sets of K Consecutive Numbers

Posted on | In ,

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into sets of k consecutive numbers
Return True if its possible otherwise return False.

Example

No.1

Input: nums = [1,2,3,3,4,4,5,6], k = 4

Output: true

Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].

No.2

Input: nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3

Output: true

Explanation: Array can be divided into [1,2,3] , [2,3,4] , [3,4,5] and [9,10,11].

No.3

Input: nums = [3,3,2,2,1,1], k = 3

Output: true

No.4

Input: nums = [1,2,3,4], k = 3

Output: false

Explanation: Each array should be divided in subarrays of size 3.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= nums.length

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public boolean isPossibleDivide(int[] nums, int k) {
    int n = nums.length;

    if (n % k != 0)
        return false;

    TreeMap<Integer, Integer> map = new TreeMap<>();

    for (int num : nums)
        map.put(num, map.getOrDefault(num, 0) + 1);

    while (!map.isEmpty()) {
        int firstNum = map.firstKey();

        for (int i = firstNum; i < firstNum + k; i++) {
            int count =  map.getOrDefault(i, 0);

            if (count < 1)
                return false;
            else if (count == 1)
                map.remove(i);
            else 
                map.replace(i, count - 1);
        }
    }

    return true;
}