JavaScript O(log n) time and O(1) space without strings


  • 0

    First, here is the version with string conversion:

    var nextGreaterElement = function(n) {
        let s = '' + n;
        let j = s.length - 1, i = j - 1;
        while (s[i + 1] <= s[i]) i--;
        if (i === -1) return -1;
        while (s[j] <= s[i]) j--;
        let right = s.substring(i + 1, j) + s[i] + s.substr(j + 1);
        let res = parseInt(s.substr(0, i) + s[j] + right.split('').reverse().join(''));
        return res < 2147483648 ? res : -1;
    };
    

    And below we reduce space to O(1). Indexes start from the right here:

    var nextGreaterElement = function(n) {
        let i = 1, a = n % 10;
        while (a <= (a = getIthDigit(n, i))) i++;
        if (a === undefined) return -1;
        
        let j = 0, b;
        while ((b = getIthDigit(n, j)) <= a) j++;
        
        let mag = Math.pow(10, i);
        n += (b - a) * mag + (a - b) * Math.pow(10, j);  // swap
        let res = n - n % mag + reverse(n, mag / 10);
        return res < 2147483648 ? res : -1;
    };
    
    function reverse(n, mag) {
        let res = 0;
        for (let i = 0; mag >= 1; i++, mag /= 10) {
            res += getIthDigit(n, i) * mag;
        }
        return res || n % 10;
    }
    
    function getIthDigit(n, i) {
        if (n = ~~(n / Math.pow(10, i))) return n % 10;
    }
    

    An analysis of the strategy can be found here.


Log in to reply
 

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