Example Walkthroughs

Suppose your number is 123475531. Start from the right and look for the first even digit that has a larger digit to its right. Swap 4 with the smallest digit greater than 4 to its right, resulting in 123575431. Move the even digit (4) to the end and sort the digits between the swapped positions in ascending order, giving 123513574.

For another example, consider 136531. If there is no even digit with a greater digit to its right, look at the next digit to the left and repeat the process. Swap and move the even digit to the end, then sort the remaining digits. This sequence could go: 136531 → 156331 → 153316 → 151336.

If the number is in descending order, such as 97654, or if there is only one even digit with no higher digit to its right, and no digits to the left have a greater digit to their right (e.g., 976173), then no solution exists.

Step-by-Step Algorithm

Let’s use N = 8234961 as an example and follow the process with added checks for even digits:

Identify the longest non-decreasing sequence from the right and split the number into X and Y. Track whether Y contains an even digit.
- For N = 8234 | 961, X = 8234, Y = 961, a = 4, and evenExist = true.
- If Y does not contain an even digit, extend Y leftward until you find one. For example, N = 425731; X = 425, Y = 731, a = 5, evenExist = false. Extend Y to get Y = 5731, X = 42, a = 2.
Find the smallest digit in Y that is greater than a. For N = 8234 | 961, a = 4, b = 6.
Swap a and b. After swapping: N = 8236 | 941; X = 8236, Y = 941.
Find the largest even digit in Y. For N = 8236 | 941, X = 8236, Y = 941, max even = 4. If there is no even digit in Y after swapping, extend Y further left until you find one. For example, 125831.
Swap the largest even digit with the rightmost digit. After swapping: N = 8236 | 914; X = 8236, Y = 914.
Sort the remaining digits in Y (except the rightmost) in ascending order. For N = 8236 | 91 | 4, after sorting: N = 8236 | 19 | 4.

The final result, N = xy, is the next even permutation.

Code

[{"language":"Java","code":"class Solution {\n    // Swap two elements in the array if indices are valid and not the same\n    private void swap(int[] a, int i, int j) {\n        if (i == j || i < 0 || j < 0 || i >= a.length || j >= a.length) {\n            return;\n        }\n        a[i] ^= a[j];\n        a[j] ^= a[i];\n        a[i] ^= a[j];\n    }\n\n    /**\n     * Finds the next even permutation of the given digits array.\n     * Returns null if no such permutation exists.\n     */\n    public int[] nextEven(int[] digits) {\n        int y = digits.length - 1;\n        boolean evenFound = digits[y] % 2 == 0;\n        // Find the longest non-increasing suffix from the right\n        for (int i = digits.length - 2; i >= 0; i--) {\n            if (digits[i] >= digits[i + 1]) {\n                evenFound |= digits[i] % 2 == 0;\n                y = i;\n            } else {\n                break;\n            }\n        }\n\n        int maxEven = -1;\n        // If the suffix does not contain an even digit, extend it left until one is found\n        while (!evenFound && y - 1 >= 0 && digits[y - 1] % 2 != 0) {\n            y--;\n        }\n\n        // If already at the largest permutation, check if last digit is even\n        if (y <= 0) {\n            return digits[digits.length - 1] % 2 == 0 ? digits : null;\n        }\n\n        // Try to extend the suffix so that it contains an even digit after swapping\n        while (y - 1 >= 0) {\n            // X = digits[0..y-1], Y = digits[y..digits.length-1]\n            // a is the last element of X\n            // Find b: the smallest digit in Y greater than a\n            int a = y - 1;\n            int b = -1;\n            for (int i = y; i < digits.length; i++) {\n                if (digits[i] > digits[a] && (b == -1 || digits[i] < digit

Related Tags

Continue Practicing