1296. Divide Array In Sets Of K

/**

 * 1296. Divide Array in Sets of K Consecutive Numbers

 *

 * 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 it is possible. Otherwise, return False.

 *

 * Example 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].

 */

See the solution on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/google/medium/DivideArrayInSet.java

Observation: The problem is asking to check if we can partition the array in groups with each having K consecutive integers. The first observation is that we need to sort the array. Second is that we need to find consecutive increasing integers so if we somehow know the first starting number, we can look for subsequent number in a map.

Logic:

1. Sort the array
2. For each integer in array add it to a map with key as integer and value as number of occurrences
3. Work on the array from left to right
   1. Keep track of the first element to start the group from in a variable
   1. From the first element move forward k elements while decrementing count of items in map
      1. Update the next beginning number for the following group
      1. If the next consequent number can’t be found, return false (sequence isn’t possible)
   1. If next beginning variable cant be found, restart from step 3 again
4. If you have reached the end of the array, return success

Here is the code:

public boolean isPossibleDivideFaster(int[] nums, int k) {
    Arrays.sort(nums);
    Map<Integer, Integer> map = new HashMap<>();
    for(int i = 0; i<nums.length; i++) {
        map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
    }
    for(int i = 0; i<nums.length; ) {
        int inc = 0;
        int num = nums[i];
        Integer nextBegin = null;
        while(inc == 0 || nextBegin != null) {
            if(nextBegin != null) {
                num = nextBegin;
            }
            nextBegin = null;
            for(int j = 1; j<=k; j++) {
                inc++;
                Integer count = map.get(num);
                if(count != null && count > 0) {
                    map.put(num, count-1);
                    if(count - 1 != 0 && nextBegin == null) {
                        nextBegin = num;
                    }
                } else {
                    return false;
                }
                num++;
            }

        }
        i += inc;
    }
    return true;
}