JavaScript O(log n) time and O(1) space using buckets


  • 0

    First, here is the common solution modified with buckets, which enables it to be single-pass (the inner loop doesn't execute unless a lesser element is found since it will start beyond the bounds of buckets):

    var nextGreaterElement = function(n) {
        let s = '' + n;
        const buckets = [];
        for (let i = s.length - 2; i >= 0; i--) {
            let d = parseInt(s[i + 1]);
            if (buckets[d] === undefined) buckets[d] = i + 1;
            for (let b = parseInt(s[i]) + 1; b < buckets.length; b++) {
                if (!buckets[b]) continue;
                let right = s.substring(i + 1, buckets[b]) + s[i] + s.substr(buckets[b] + 1);
                let res = parseInt(s.substr(0, i) + b + right.split('').reverse().join(''));
                return res < 2147483648 ? res : -1;
            }
        }
        return -1;
    };
    
    1. Starting from the right (except for the last digit), if a digit has a larger digit anywhere to the right of it, swap it with the minimum such digit. (buckets[b] stores the right-most index at which the digit b occurred, of the digits seen so far.) For example, 12443322 turns into 13443222.
    2. Reverse the right-side digits, so 13443222 turns into 13222344.

    The time complexity is O(d) in the number of digits of n which is O(log n) in the magnitude of n. O(d) or O(log n) space is used for the string manipulation. The buckets use constant time and space since there will be a maximum of 10 of them. We could have stored the left-most index and used sort, but that would slow us down to O(d log d) or O((log n) log log n).

    We could have also stored the count of each seen right-side digit instead of the index:

    var nextGreaterElement = function(n) {
        let s = '' + n;
        const buckets = [];
        for (let i = s.length - 2; i >= 0; i--) {
            let d = parseInt(s[i + 1]);
            buckets[d] = (buckets[d] || 0) + 1;  
            d = parseInt(s[i]);
            for (let b = d + 1; b < buckets.length; b++) {
                if (!buckets[b]) continue;
                buckets[b]--;  // there is one less `b` on the right side after swap...
                buckets[d] = (buckets[d] || 0) + 1;  // ...and one more `d`
                let res = parseInt(s.substr(0, i) + b + buckets.reduce((right, c, d) => right + ('' + d).repeat(c || 0), ''));
                return res < 2147483648 ? res : -1;
            }
        }
        return -1;
    };
    

    There isn't any speed advantage there except it makes our final solution easier to write. We can reduce space to O(1) using arithmetic instead of strings. Our final solution is:

    var nextGreaterElement = function(n) {
        for (let buckets = []; n >= 10; n = Math.floor(n / 10)) {
            let d = n % 10;
            buckets[d] = (buckets[d] || 0) + 1;  
            d = Math.floor(n / 10) % 10;
            for (let b = d + 1; b < buckets.length; b++) {
                if (!buckets[b]) continue;
                buckets[b]--;
                buckets[d] = (buckets[d] || 0) + 1;
                let res = 0, col = 0;
                for (let d = buckets.length - 1; d >= 0; d--) {
                    for (let i = 0; i < (buckets[d] || 0); i++) {
                         res += d * Math.pow(10, col++);
                    }
                }
                res += b * Math.pow(10, col++);
                for (n = Math.floor(n / 100); n; n = Math.floor(n / 10)) {
                    res += (n % 10) * Math.pow(10, col++);
                }
                return res < 2147483648 ? res : -1;
            }
        }
        return -1;
    };
    

    The version without buckets can be found here.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.