Find next greater number with same set of digits

The problem, simply

You get a number as a string of n digits. Rearrange its digits to make the smallest number that is still bigger than it. If no rearrangement is bigger, return -1 (or "not possible").

For 534976 the answer is 536479. For 4321 the digits already go down, which is the biggest order, so the answer is -1.

A story to remember it

Picture it

Examples

Way 1: the simple way

Make every arrangement of the digits and keep the smallest one that is bigger than n.

1. Build all orders of the digits with backtracking.
2. For each order that is bigger than n, keep it if it is smaller than the best so far.
3. Return the best, or -1.

class Solution {
    private String best;

    public String nextGreater(String n) {
        best = null;
        build(n.toCharArray(), new boolean[n.length()], new StringBuilder(), n);
        return best == null ? "-1" : best;
    }

    private void build(char[] d, boolean[] used, StringBuilder cur, String n) {
        if (cur.length() == d.length) {
            String s = cur.toString();
            // same length, so comparing as text is the same as comparing as numbers
            if (s.compareTo(n) > 0 && (best == null || s.compareTo(best) < 0)) best = s;
            return;
        }
        for (int k = 0; k < d.length; k++) {
            if (used[k]) continue;
            used[k] = true;
            cur.append(d[k]);
            build(d, used, cur, n);          // try every digit in this place
            cur.deleteCharAt(cur.length() - 1);
            used[k] = false;
        }
    }
}

How long it takes: n! orders, each built and compared in O(n), so O(n! * n). Ten digits already means over 36 million orders. Extra room: the order being built and the call stack, O(n).

Way 2: the clever way

Change as little as possible, as far to the right as possible.

1. Walk from the right and find the first spot i where d[i] < d[i + 1]. That is the dip. Everything after it goes down. If there is no dip, return -1.
2. Walk from the right again and find the first digit d[j] bigger than d[i]. Because the tail goes down, it is the smallest digit in the tail that is still bigger than d[i].
3. Swap d[i] and d[j]. The tail still goes down.
4. Flip the tail so it goes up. That makes it as small as possible.

class Solution {
    public String nextGreater(String n) {
        char[] d = n.toCharArray();
        int i = d.length - 2;
        while (i >= 0 && d[i] >= d[i + 1]) i--;   // find the dip from the right
        if (i < 0) return "-1";                    // digits only go down: no answer

        int j = d.length - 1;
        while (d[j] <= d[i]) j--;                  // smallest bigger digit in the tail
        swap(d, i, j);

        for (int a = i + 1, b = d.length - 1; a < b; a++, b--) {
            swap(d, a, b);                         // flip the tail so it goes up
        }
        return new String(d);
    }

    private void swap(char[] d, int a, int b) {
        char t = d[a]; d[a] = d[b]; d[b] = t;
    }
}

How long it takes: at most two walks and one flip over the digits, O(n). Extra room: the digit array, which is the answer itself, so O(1) extra.

Watch out for

• Use >= when looking for the dip and <= when looking for j. Strict tests break on repeated digits: with > the search on 1222 stops at a fake dip and runs off the front, and with < the number 151 swaps a 1 with the other 1 and returns 115.
• When the input is an int (LeetCode 556), the answer may not fit. The next arrangement of 2147483486 is 2147483648, one more than the largest int, so the answer must be -1. Build it as a long and check.
• No dip means the digits are in going down order, the biggest arrangement. Return -1, do not wrap around.

What interviewers ask next

• Next permutation of an array in place (LeetCode 31)? The same steps. When there is no dip, flip the whole array to get the smallest arrangement.
• The previous smaller number? Mirror every step: find the first d[i] > d[i + 1] from the right, swap with the biggest digit in the tail that is smaller than d[i], then flip the tail.
• The k-th next arrangement, or the k-th arrangement of 1..n? Calling next k times is slow. Use counting: each first digit leads (n - 1)! arrangements, so pick digits with division and remainder.
• Why is this the very next one? Everything left of the dip stays the same, the dip grows by the smallest possible step, and the tail becomes the smallest possible tail. Nothing can fit between.

Remember this

Grown-up words: an arrangement of the digits is a permutation, the very next arrangement is the next lexicographic permutation, the dip is the pivot, and the tail that only goes down is a non-increasing suffix.