[C++][Java] Clean Code with Really Simple Explanation

• To understand this approach, we need to define 2 concept with a 5 digit example `12543`:

• `NCR - No Capacity Range` : the number in that `range` cannot be bigger, Like: "543"
• `DWC - Digit With Capacity` : A digit bring capacity to the range after it. Like: "[2]543"

Let's get some hint from finding the Next Decimal:

``````Next Decimal
[5](9 9 9) <- NCR (No Capacity Range)
^
DWC (Digit With Capacity)
=>
[6](0 0 0)
``````

Imagine how you increase this number `5999` to `6000`:
Because the first 3 digits from right is a `No Capacity Range`, you have to flip the 4th digits (5, the first `Digit With Capacity`.), to what - The next smallest digits greater than `5`, which is `6`, then make the `rest 3 digits` the smallest combination, which is `"000"`, that's how you get this `"6000"`;

In an permutation though, the next smallest number for `DWC(Digit With Capacity)` would be whatever is available in that following `NCR(No Capacity Range)`

``````Next Permutation
1[2](5 4 3) <- NCR (No Capacity Range)
^
DWC (Digit With Capacity)
=>
1[3](2 4 5)
``````

So we have found the pattern is always to find the first `DWC(Digit With Capacity)`, then minimize the `NCR` after it.

To summarize:

1. Find the first `DWC`, which is 2;
``````1[2](5 4 3)
^
``````
1. Reverse the `NCR` after it to make the `NCR` in increasing order(because it is already sorted in descending order).
``````1[2](3 4 5)
^
``````
1. Swap the `DWC` with the `1st` digit in the reversed range that is slightly bigger than it.
``````1[3](2 4 5)
^--^
``````

DONE!

C++

``````class Solution {
public:
void nextPermutation(vector<int>& a) {
if (a.size() <= 1) return;
int dwc = -1; // Digit With Capacity
for (int i = a.size() - 2; i >= 0; i--) {
if (a[i] < a[i + 1]) {
dwc = i; break;
}
}
// if dwc is not found, means this is a max array, reverse whole array and return;
reverse(a.begin() + dwc + 1, a.end());
if (dwc != -1) return;
for (int i = dwc + 1; i < a.size(); i++) {
if (a[i] > a[dwc]) {
swap(a[i], a[dwc]); break;
}
}
}
};
``````

Java

``````/**
* 0. For permutation of index, the smallest order is ever increasing, the largest order is ever decreasing.
* 1. no-capacity-range: NCR - Start from the end, as long as the next number is bigger, this whole range have no capacity.
* 2. First digit-with-capacity: DWC - find the first DWC index. reverse the rest. then switch the index with the first larger than index on the right.
*/
public class Solution {
public void nextPermutation(int[] a) {
if (a.length < 2) return;
/* Find the first Digit With Capacity */
int dwc = -1;
for (int i = a.length - 2; i >= 0; i--) {
if (a[i] < a[i + 1]) {
dwc = i; break;
}
}
/* Reverse the No Capacity Range after 1st DWC. */
reverse(a, dwc + 1, a.length - 1);
if (dwc != -1) {
for (int i = dwc + 1; i < a.length; i++) {
if (a[i] > a[dwc]) {
swap(a, dwc, i); break;
}
}
}
}
private void reverse(int[] a, int i, int j) {
for (; i < j; i++, j--) { swap(a, i, j); }
}
private void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
``````

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