Next greater number with the same set of digits

Medium

Problem

Given a number as a string of digits, return the smallest number greater than it that uses exactly the same digits, or "no greater number" if none exists.

Example 1

Input:  "218765"
Output: "251678"

Example 2

Input:  "4321"
Output: "no greater number"

Also asked as: Find next greater number with same set of digits

Test cases

Case 1

Input:    "218765"
Expected: "251678"

Case 2

Input:    "534976"
Expected: "536479"

Case 3

Input:    "1234"
Expected: "1243"

Case 4

Input:    "4321"
Expected: "no greater number"

Case 5

Input:    "7"
Expected: "no greater number"

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Next permutation on the digit array

Time O(d)Space O(d)

Identical to "next permutation": find the rightmost ascending pair, swap with the next-larger digit to its right, reverse the suffix.

function nextGreater(numStr) {
const a = [...numStr];
let i = a.length - 2;
while (i >= 0 && a[i] >= a[i + 1]) i--;
if (i < 0) return 'no greater number';
let j = a.length - 1;
while (a[j] <= a[i]) j--;
[a[i], a[j]] = [a[j], a[i]];
return a.slice(0, i + 1).join('') + a.slice(i + 1).reverse().join('');
}