846. Hand of Straights, 1296. Divide Array in Sets of K Consecutive Numbers

use treeMap

T: O(nlogn*k)

S: O(n)

class Solution {
    public boolean isPossibleDivide(int[] nums, int k) {
        int n = nums.length;
        if (n%k != 0) {
            return false;
        }
        TreeMap<Integer, Integer> map = new TreeMap<>(); // num, count
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        
        for (int key : map.keySet()) {
            if (map.get(key) > 0) {
                for (int i = k - 1; i >= 0; i--) {
                    if (map.getOrDefault(key+i, 0) < map.get(key)) {
                        return false;
                    }
                    map.put(key + i, map.getOrDefault(key+i, 0) - map.get(key));
                }
            }
            
        }
        return true;
    }
}

/*
sets of k consecutive numbers.

array is size k 

Divide to one more array

use treeMap, sort and get freq map

[1,2,3,3,4,4,5,6]

after sort and get freq map

1 1 2 2 1 1 => count
1 2 3 4 5 6 => nums
[     ] k = 4

after subtract with nums[0] = 1
0 0 1 1 1 1
1 2 3 4 5 6

subtract with nums[2] = 1
0 0 1 1 1 1
1 2 3 4 5 6
    [     ]
*/

use hashmap + min, max value

T: O(n*k)

S: O(n)

class Solution {
    public boolean isNStraightHand(int[] nums, int k) {
        int m = nums.length, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        if (m % k != 0) {
            return false;
        }
        
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) {
            min = Math.min(min, n);
            max = Math.max(max, n);
            map.put(n, map.getOrDefault(n, 0) + 1);
        }

        // 少掉 sort 的關鍵在於知道 min, max, 所以就可以檢查 [min, max] 區間內連續的值的結果
        for (int i = min; i <= max; i++) {
            if (map.getOrDefault(i, 0) < 0) { // < 0 代表缺數
                return false;  // lacks
            }
            if (map.getOrDefault(i, 0) == 0) {// == 0 pass
                continue;
            }
            // 不符 sliding win
            if (max - i + 1 < k) { // i = 3, 6-3+1 = 4 ==k 還行, i = 4 就不夠了
                return false;  // extras, won't make k subset;
            }
            // 一樣倒著檢查
            // i = 3, j = 3+4-1 = 6, 6 to 3
            for (int j = i + k - 1; j >= i; j--) {
                map.put(j, map.getOrDefault(j, 0) - map.get(i));
            }
        }
        return true;
    }
}

/*
[1,2,3,3,4,4,5,6]
4

ans
[1,2,3,4] 和 [3,4,5,6]

有點 sliding window feel
 1 1 2 2 1 1 => count
[1,2,3,4,5,6]
 [     ]
     [      ]   
*/

HashMap + Sort

T: O(n + nlogn + n*k)

S: O(n)

class Solution {
    public boolean isPossibleDivide(int[] nums, int k) {

        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0)+1);
        }
        Arrays.sort(nums);
        for (int j = 0; j < nums.length; j++) {
            if (map.get(nums[j]) == 0) {
                continue;
            }
            for (int i = 1; i < k; i++) {
                int nextNum = nums[j] + i;
                if (!map.containsKey(nextNum) || map.get(nextNum) == 0) {
                    return false;
                }
            }
            for (int i = 0; i < k; i++) {
                int updateNum = nums[j] + i;
                map.put(updateNum, map.get(updateNum) - 1);
            }
        }
        return true;
    }
}

Find Roots (amazing solution)

T: O(n)

S: O(n)

```java
public class Solution {
    public boolean isPossibleDivide(int[] nums, int k) {
        Map<Integer, Integer> countMap = new HashMap<>();
        Queue<Integer> roots = new LinkedList<>();

        // Count occurrences of each number
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        // Identify potential "roots"
        for (int num : nums) {
            if (!countMap.containsKey(num - 1)) {
                roots.offer(num);
            }
        }
        System.out.println(roots.toString());
        // Test each "root"
        while (!roots.isEmpty()) {
            int root = roots.poll();
            if (countMap.get(root) == 0) {
                continue;
            }

            // Attempt to build a sequence from root to root + k
            for (int i = root; i <= root + k; i++) {
                if (i < root + k) {
                    if (!countMap.containsKey(i) || countMap.get(i) == 0) {
                        return false;
                    }

                    // Decrement the count for this number
                    countMap.put(i, countMap.get(i) - 1);
                }

                // check to root+k (aka next start for previous k consecuitive numbers)
                // Identify new "roots"
                // ex: 1 2 3 "4". (k = 3), we check this 4 has count
                if (countMap.containsKey(i) && countMap.get(i) > 0 && (!countMap.containsKey(i-1) || countMap.get(i-1) == 0)) {
                    roots.offer(i);
                }
            }
        }

        return true;
    }
}
```