Divide Array in Sets of K Consecutive Numbers

• First, perform a preliminary check: if the length of the array nums is not divisible by k, it's impossible to partition it, so return false.
• Sort the array nums in ascending order.
• Use a boolean array used of the same size as nums to keep track of which numbers have already been placed into a group. Initially, all elements are marked as not used.
• Iterate through the sorted array nums from left to right. For each number nums[i]:
  • If nums[i] has already been used (i.e., used[i] is true), skip it.
  • If it's not used, we try to form a new group of k consecutive numbers starting with nums[i].
  • We search for the next k-1 consecutive numbers (nums[i]+1, nums[i]+2, ..., nums[i]+k-1) in the rest of the array.
  • For each required number, we perform a linear scan from the position i+1. If we find the required number nums[j] and it hasn't been used yet, we mark it as used (used[j] = true) and continue searching for the next number in the sequence.
  • If any of the k-1 consecutive numbers cannot be found, it's impossible to form the required groups, so we return false.
• If we successfully iterate through the entire array and group all numbers, return true.

The brute-force method begins by sorting the input array nums. This brings numbers that could potentially form a consecutive sequence close to each other. An essential pre-condition is that the array's length must be a multiple of k; otherwise, a valid partition is impossible. We use an auxiliary boolean array, used, to track which elements have been assigned to a set. We iterate through each element of the sorted array. If an element nums[i] hasn't been used, we treat it as the start of a new potential set. We then attempt to find the subsequent k-1 consecutive integers (nums[i]+1, nums[i]+2, etc.) by scanning the rest of the array. If we find a required integer that is not yet used, we mark it as used and proceed to look for the next one. If at any point a required integer for a sequence cannot be found, we conclude that a valid partition is not possible and return false. If we manage to group all numbers this way, we return true.

1import java.util.Arrays;2 3class Solution {4    public boolean isPossibleDivide(int[] nums, int k) {5        int n = nums.length;6        if (n % k != 0) {7            return false;8        }9        Arrays.sort(nums);10        boolean[] used = new boolean[n];11        12        for (int i = 0; i < n; i++) {13            if (used[i]) {14                continue;15            }16            17            // Start a new group with nums[i]18            used[i] = true;19            int needed = k - 1;20            int lastNum = nums[i];21            22            if (needed > 0) {23                for (int j = i + 1; j < n; j++) {24                    if (!used[j] && nums[j] == lastNum + 1) {25                        used[j] = true;26                        lastNum = nums[j];27                        needed--;28                        if (needed == 0) {29                            break;30                        }31                    }32                }33            }34 35            if (needed > 0) {36                return false;37            }38        }39        40        return true;41    }42}

• First, check if nums.length % k != 0. If so, return false.
• Create a HashMap<Integer, Integer> to store the frequency of each number in nums.
• Sort the input array nums in ascending order.
• Iterate through each num in the sorted nums array:
  • If the frequency of num in the map is 0, it means it has already been used in another sequence, so we continue.
  • If the frequency is greater than 0, num must be the start of a new sequence.
  • For this new sequence, check for the existence of num, num+1, ..., num+k-1.
  • Iterate from i = 0 to k-1. For each currentNum = num + i:
    • If currentNum is not in the map or its count is 0, return false.
    • Decrement the count of currentNum in the map.
• If the entire loop completes, it means all numbers have been successfully grouped. Return true.

A more efficient way to solve the problem is to use a hash map to count the occurrences of each number. This avoids the expensive O(N) scans to find numbers for a sequence. The algorithm is as follows:

1. Perform the initial check: if nums.length is not divisible by k, return false.
2. Populate a hash map with the frequencies of each number in the nums array. This takes O(N) time.
3. Sort the original nums array. This is a key step, as it allows us to process potential sequences in an orderly fashion. By iterating through the sorted array, whenever we encounter a number that can start a sequence, we know it's the smallest possible start for any remaining available numbers.
4. Iterate through the sorted nums. For each number num, check its count in the frequency map. If the count is zero, it has already been consumed by a previous sequence, so we skip it. If the count is positive, we treat num as the beginning of a new sequence. We then verify that we have enough cards for the entire sequence of k (i.e., num, num+1, ..., num+k-1) by checking their counts in the map. If any number is missing, we return false. Otherwise, we decrement the counts for all k numbers in the map and continue.

If we successfully process every number, we return true.

1import java.util.Arrays;2import java.util.HashMap;3import java.util.Map;4 5class Solution {6    public boolean isPossibleDivide(int[] nums, int k) {7        if (nums.length % k != 0) {8            return false;9        }10        Map<Integer, Integer> counts = new HashMap<>();11        for (int num : nums) {12            counts.put(num, counts.getOrDefault(num, 0) + 1);13        }14        Arrays.sort(nums);15        for (int num : nums) {16            if (counts.get(num) == 0) {17                continue;18            }19            for (int i = 0; i < k; i++) {20                int currentNum = num + i;21                if (counts.getOrDefault(currentNum, 0) == 0) {22                    return false;23                }24                counts.put(currentNum, counts.get(currentNum) - 1);25            }26        }27        return true;28    }29}

• First, check if nums.length % k != 0. If so, return false.
• Create a TreeMap<Integer, Integer> to store the frequency of each number. A TreeMap automatically keeps the keys (the numbers) in sorted order.
• While the TreeMap is not empty:
  • Get the smallest key (the first number) from the map, let's call it start.
  • Get its frequency, count.
  • This start must begin count new sequences.
  • Iterate from i = 0 to k-1. For each currentNum = start + i:
    • Check if the map has currentNum and if its frequency is at least count. If not, return false.
    • Update the frequency of currentNum by subtracting count.
    • If the new frequency of currentNum is 0, remove it from the map. This is a key optimization.
• If the loop finishes (map becomes empty), return true.

This optimal approach leverages a TreeMap, which is a sorted map data structure. It combines the frequency counting and sorting steps efficiently.

1. As always, we first check if nums.length is divisible by k.
2. We populate a TreeMap with the numbers from the input array as keys and their frequencies as values. The TreeMap automatically maintains the keys in ascending order. This costs O(N log U) time, where U is the number of unique elements.
3. We then enter a loop that continues as long as the map is not empty.
4. In each iteration, we retrieve the smallest key (start) from the map. This is an O(log U) operation. This start number is guaranteed to be the smallest available number that can begin a sequence.
5. We get its frequency, count. This means we must form count sequences starting with start.
6. We then check if we can form count full sequences. We iterate from i = 0 to k-1, checking if the map contains start + i with a frequency of at least count. If this condition fails for any number in the sequence, we return false.
7. If all numbers for the count sequences are available, we decrement their frequencies in the map by count. If a number's frequency drops to zero, we remove it from the map. This removal is crucial for efficiency, as it ensures the next firstKey() call correctly gives us the next smallest number that needs to start a sequence.

If the map becomes empty, it means all numbers were successfully partitioned, and we return true.

1import java.util.TreeMap;2import java.util.Map;3 4class Solution {5    public boolean isPossibleDivide(int[] nums, int k) {6        if (nums.length % k != 0) {7            return false;8        }9        Map<Integer, Integer> counts = new TreeMap<>();10        for (int num : nums) {11            counts.put(num, counts.getOrDefault(num, 0) + 1);12        }13        14        while (!counts.isEmpty()) {15            int start = ((TreeMap<Integer, Integer>) counts).firstKey();16            int count = counts.get(start);17            18            for (int i = 0; i < k; i++) {19                int currentNum = start + i;20                if (counts.getOrDefault(currentNum, 0) < count) {21                    return false;22                }23                counts.put(currentNum, counts.get(currentNum) - count);24                if (counts.get(currentNum) == 0) {25                    counts.remove(currentNum);26                }27            }28        }29        30        return true;31    }32}