Problem

Given a number represented as nums array. Find the smallest even number greater than N such that the digits are a permutation of the number N.

Examples

Example 1

1
2

Input: nums = [3,4,7,2,2,6,4,1]
Output: [3,4,7,2,4,1,2,6]

Example 2

1
2

Input: nums = [1,1,1]
Output: [-1]

Example 3

1
2

Input: nums = [1,1,2,3]
Output: [1,1,3,2]

Solution

Method 1 - Naive

The most straightforward approach is to generate every possible permutation of the digits, sort them, and then find the smallest even permutation that is greater than the original number. While this method is simple to understand, it is extremely inefficient due to the exponential number of permutations involved.

We can improve on this by analyzing the problem more closely and developing an algorithm that avoids generating all permutations. Before that, let’s first consider how to find the next permutation in lexicographical order.

Complexity

⏰ Time complexity: O(n!) — Generating all permutations of n digits is factorial in time. 🧺 Space complexity: O(n!) — Storing all permutations also requires factorial space.

Method 2 - Tweaking Next Permutation

Let’s first revisit how to find the next permutation, and then see how to adapt it for the next even permutation. For a full explanation, see Next permutation of a number.

To find the next permutation, start from the right and look for the first digit that is smaller than the digit immediately after it. For example, with the number 12344875, the first such digit from the right is 4.

Next, scan to the right of this digit to find the smallest digit that is larger than 4—in this case, it’s 5 in the sequence 875. Swap these two digits, resulting in 12345874.

After swapping, sort all digits to the right of the swapped position in ascending order. This gives 12345784, which is the next permutation in lexicographical order. However, this process does not guarantee the result is even.

To ensure the next permutation is even, you need to adjust the process. If the last digit after swapping and sorting is even, you’re done. If not, you need to permute the digits to get an even number at the end.

For example, if the last digit is not even, look for the rightmost even digit that can be swapped to the end, and rearrange the remaining digits to get the smallest possible even permutation greater than the original.

If there is no such even digit, or the number is already the largest permutation, then no valid next even permutation exists.

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:

  1. 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.
  2. Find the smallest digit in Y that is greater than a. For N = 8234 | 961, a = 4, b = 6.
  3. Swap a and b. After swapping: N = 8236 | 941; X = 8236, Y = 941.
  4. 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.
  5. Swap the largest even digit with the rightmost digit. After swapping: N = 8236 | 914; X = 8236, Y = 914.
  6. 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

class Solution {
    // Swap two elements in the array if indices are valid and not the same
    private void swap(int[] a, int i, int j) {
        if (i == j || i < 0 || j < 0 || i >= a.length || j >= a.length) {
            return;
        }
        a[i] ^= a[j];
        a[j] ^= a[i];
        a[i] ^= a[j];
    }

    /**
     * Finds the next even permutation of the given digits array.
     * Returns null if no such permutation exists.
     */
    public int[] nextEven(int[] digits) {
        int y = digits.length - 1;
        boolean evenFound = digits[y] % 2 == 0;
        // Find the longest non-increasing suffix from the right
        for (int i = digits.length - 2; i >= 0; i--) {
            if (digits[i] >= digits[i + 1]) {
                evenFound |= digits[i] % 2 == 0;
                y = i;
            } else {
                break;
            }
        }

        int maxEven = -1;
        // If the suffix does not contain an even digit, extend it left until one is found
        while (!evenFound && y - 1 >= 0 && digits[y - 1] % 2 != 0) {
            y--;
        }

        // If already at the largest permutation, check if last digit is even
        if (y <= 0) {
            return digits[digits.length - 1] % 2 == 0 ? digits : null;
        }

        // Try to extend the suffix so that it contains an even digit after swapping
        while (y - 1 >= 0) {
            // X = digits[0..y-1], Y = digits[y..digits.length-1]
            // a is the last element of X
            // Find b: the smallest digit in Y greater than a
            int a = y - 1;
            int b = -1;
            for (int i = y; i < digits.length; i++) {
                if (digits[i] > digits[a] && (b == -1 || digits[i] < digits[b])) {
                    b = i;
                }
            }

            // If no valid b found, check if last digit is even
            if (b == -1) {
                return digits[digits.length - 1] % 2 == 0 ? digits : null;
            }
            // Swap a and b
            swap(digits, a, b);

            // Find the largest even digit in the suffix
            maxEven = -1;
            for (int i = y; i < digits.length; i++) {
                if (digits[i] % 2 == 0 && (maxEven == -1 || digits[i] > digits[maxEven])) {
                    maxEven = i;
                }
            }

            // If no even digit found, extend the suffix further left
            if (maxEven == -1) {
                y--;
            } else {
                break;
            }
        }

        if (maxEven == -1) {
            return digits[digits.length - 1] % 2 == 0 ? digits : null;
        }

        // Swap the largest even digit with the rightmost digit
        swap(digits, maxEven, digits.length - 1);
        // Sort the suffix except the rightmost digit
        Arrays.sort(digits, y, digits.length - 1);

        return digits;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#include <vector>
#include <algorithm>

class Solution {
private:
    // Swap two elements in the array if indices are valid and not the same
    void swap(std::vector<int>& a, int i, int j) {
        if (i == j || i < 0 || j < 0 || i >= a.size() || j >= a.size()) return;
        std::swap(a[i], a[j]);
    }

public:
    // Finds the next even permutation of the given digits array.
    // Returns empty vector if no such permutation exists.
    std::vector<int> nextEven(std::vector<int> digits) {
        int y = digits.size() - 1;
        bool evenFound = digits[y] % 2 == 0;
        // Find the longest non-increasing suffix from the right
        for (int i = digits.size() - 2; i >= 0; i--) {
            if (digits[i] >= digits[i + 1]) {
                evenFound |= digits[i] % 2 == 0;
                y = i;
            } else {
                break;
            }
        }

        int maxEven = -1;
        // If the suffix does not contain an even digit, extend it left until one is found
        while (!evenFound && y - 1 >= 0 && digits[y - 1] % 2 != 0) {
            y--;
        }

        // If already at the largest permutation, check if last digit is even
        if (y <= 0) {
            return digits[digits.size() - 1] % 2 == 0 ? digits : std::vector<int>();
        }

        // Try to extend the suffix so that it contains an even digit after swapping
        while (y - 1 >= 0) {
            int a = y - 1;
            int b = -1;
            for (int i = y; i < digits.size(); i++) {
                if (digits[i] > digits[a] && (b == -1 || digits[i] < digits[b])) {
                    b = i;
                }
            }
            if (b == -1) {
                return digits[digits.size() - 1] % 2 == 0 ? digits : std::vector<int>();
            }
            swap(digits, a, b);

            maxEven = -1;
            for (int i = y; i < digits.size(); i++) {
                if (digits[i] % 2 == 0 && (maxEven == -1 || digits[i] > digits[maxEven])) {
                    maxEven = i;
                }
            }
            if (maxEven == -1) {
                y--;
            } else {
                break;
            }
        }

        if (maxEven == -1) {
            return digits[digits.size() - 1] % 2 == 0 ? digits : std::vector<int>();
        }

        swap(digits, maxEven, digits.size() - 1);
        std::sort(digits.begin() + y, digits.end() - 1);

        return digits;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

from typing import List

class Solution:
    def swap(self, a: List[int], i: int, j: int):
        if i == j or i < 0 or j < 0 or i >= len(a) or j >= len(a):
            return
        a[i], a[j] = a[j], a[i]

    def nextEven(self, digits: List[int]) -> List[int] or None:
        y = len(digits) - 1
        even_found = digits[y] % 2 == 0
        # Find the longest non-increasing suffix from the right
        for i in range(len(digits) - 2, -1, -1):
            if digits[i] >= digits[i + 1]:
                even_found |= digits[i] % 2 == 0
                y = i
            else:
                break

        max_even = -1
        # If the suffix does not contain an even digit, extend it left until one is found
        while not even_found and y - 1 >= 0 and digits[y - 1] % 2 != 0:
            y -= 1

        # If already at the largest permutation, check if last digit is even
        if y <= 0:
            return digits if digits[-1] % 2 == 0 else None

        # Try to extend the suffix so that it contains an even digit after swapping
        while y - 1 >= 0:
            a = y - 1
            b = -1
            for i in range(y, len(digits)):
                if digits[i] > digits[a] and (b == -1 or digits[i] < digits[b]):
                    b = i
            if b == -1:
                return digits if digits[-1] % 2 == 0 else None
            self.swap(digits, a, b)

            max_even = -1
            for i in range(y, len(digits)):
                if digits[i] % 2 == 0 and (max_even == -1 or digits[i] > digits[max_even]):
                    max_even = i
            if max_even == -1:
                y -= 1
            else:
                break

        if max_even == -1:
            return digits if digits[-1] % 2 == 0 else None

        self.swap(digits, max_even, len(digits) - 1)
        digits[y:len(digits) - 1] = sorted(digits[y:len(digits) - 1])

        return digits

Complexity

⏰ Time complexity: O(n^2) — The algorithm may scan and sort subarrays multiple times in the worst case. 🧺 Space complexity: O(n) — Uses extra space for the digits array/list and sorting.