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

• 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.

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