Check the sequences in the array JS

user_11069163 0
Viewed 88

I'm tying to solve an "easy" problem from LeetCode, called Divide Array in Sets of K Consecutive Numbers, but can not find a way of how to check the sequences. From my point of view it will be to many loops:

const isPossibleDivide = (nums, k) => {
    const sorted = nums.sort((a, b) => a - b)
    const counts = {}
    sorted.forEach(item => counts[item] = (counts[item] || 0) + 1)

    // the problem part
    Object.entries(counts).map(([key, value]) => {
        if (value !== 0) {
            counts[key] = value - 1
        }
    })
    console.log(counts)
}

isPossibleDivide([3, 2, 1, 2, 3, 4, 3, 4, 5, 9, 10, 11], 3)
algorithm javascript
2 Answers

For this problem, we'd use a map. This'll pass through:

const isPossibleDivide = (nums, k) => {
    if (!nums.length % k) {
        return false;
    }

    const headsMap = new Map();

    for (const num of nums) {
        headsMap.set(num, headsMap.has(num) ? -~headsMap.get(num) : 1);
    }

    for (let head of nums) {
        if (headsMap.get(head) === 0) {
            continue;
        }

        while (headsMap.get(--head) > 0);
        ++head;
        const count = headsMap.get(head);
        for (let index = 1; index < k; ++index) {
            const curr = headsMap.get(head + index)
            if (curr === undefined || curr < count) {
                return false;
            }

            headsMap.set(head + index, curr - count);
        }

        headsMap.set(head, 0);
    }

    return true;
};

If we would be able to use deque, this python version would help:

from typing import List

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int):
        count_map = collections.Counter(nums)
        heads_map = collections.deque()
        last_checked = -1
        opened = 0

        for key in sorted(count_map):
            if opened > count_map[key] or opened > 0 and key > -~last_checked:
                return False
            heads_map.append(count_map[key] - opened)
            last_checked = key
            opened = count_map[key]

            if len(heads_map) == k:
                opened -= heads_map.popleft()

        return opened == 0

In Java, we could use TreeMap and LinkedList:

public class Solution {
    public static final boolean isPossibleDivide(int[] nums, int k) {
        Map<Integer, Integer> countMap = new TreeMap<>();

        for (int num : nums) {
            countMap.put(num, -~countMap.getOrDefault(num, 0));
        }

        Queue<Integer> headsMap = new LinkedList<>();

        int lastChecked = -1;
        int opened = 0;

        for (int key : countMap.keySet()) {
            if (opened > 0 && key > -~lastChecked || opened > countMap.get(key)) {
                return false;
            }

            headsMap.add(countMap.get(key) - opened);
            lastChecked = key;
            opened = countMap.get(key);

            if (headsMap.size() == k) {
                opened -= headsMap.remove();
            }
        }

        return opened == 0;
    }
}

References

  • For additional details, you can see the Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis1, 2 in there.
user_65533280 
var isPossibleDivide = (array,k)=>{
    const map = new Map()
    if(array.length%k !== 0){
        return false
    }
    for(let i = 0 ; i < array.length ; ++i ){
        if(map[array[i]]===undefined){
            map[array[i]] = 1
        }
        else{
            map[array[i]] = map[array[i]] + 1
        }
    }


    for(let key in map){
        x = map[key];
        if( x === 0 ){
            continue
        }
        for(let j = Number(key) + 1 ; j <  Number(key) + k ; ++j ){
            if(map[ j ] === undefined || x > map[ j ]){
                return false
            }
            map[j] = map[j] - x
        }
    }
    return true

}
user_79006100
Related