Smallest Missing Non-negative Integer After Operations

main.md

Leetcode #2598

Approach

Didn't realize at first that each elements in the nums array has to be unique after performing an operation. My first step was to build a mod array to store the least non-negative number that can be formed from each nums element. Then sorted the mod array, if first element in the sorted array isn't 0, then 0 is our smallest mex.

For cases of repeting numbers in our mod array, we build a frequency map, with the frequencies being "0-indexed", then I modifed the mod array elements using their freq. count, (adding value * freq to the mod element).

Then a second sort, to keep the elements in the mod array in increasing order, to make iteration easy.

I then iterated over the mod array, looking for where the adjacent elements are non-consecutive, where the current_number+1 will be the maximum MEX that satisfies the stated conditions

/**
 * @param {number[]} nums
 * @param {number} value
 * @return {number}
 */
var findSmallestInteger = function(nums, value) {
    let mod = nums.map(el => {
        if(el % value == -0) {
            return 0;
        } else if(el % value < 0) {
            return el % value + value
        } else {
            return el % value
        }
    })

    mod.sort((a,b) => a-b);
    
    if(mod[0] != 0) return 0;

    let obj = {}

    mod.forEach(el => {
        if(obj[el] == undefined) {
            obj[el] = -1;
        }

        obj[el] += 1;
    })

    for(let i = 1; i < mod.length; i++) {
        if(obj[mod[i]] > 0) {
            let curr = mod[i];
            mod[i] += (obj[mod[i]]) * value;
            obj[curr] -= 1;
        }
    }

    mod.sort((a,b) => a-b);

    for(let i = 0; i < mod.length - 1; i++) {
        if(mod[i] + 1 != mod[i+1]) {
            return mod[i] + 1;
        }
    }

    return mod.at(-1) + 1;
};

Complexities

Space complexity: O(N)

Time Complexity: O(NlogN)