Compute The Next Permutation of A Numeric Sequence - Case Analysis ("Next Permutation" on Leetcode)

Free 5-Day Mini-Course: https://backtobackswe.com Try Our Full Platform: https://backtobackswe.com/pricing 📹 Intuitive Video Explanations 🏃 Run Code As You Learn 💾 Save Progress ❓New Unseen Questions 🔎 Get All Solutions Question: Given a permutation of a sequence, calculate the next permutation in that sequence (if the permutation given is the last one, just return an empty array since it has no next permutation...it is the last permutation). Approach 1 (Brute Force) We can compute all permutations and stop on the permutation right after the permutation given. This can have us generate n! permutations in the worst case (the permutation given is the last one). Approach 2 (Use Intuition & Patterns) Permutation Sequence Example: [0, 1, 2] 1.) [0, 1, 2] 2.) [0, 2, 1] 3.) [1, 0, 2] 4.) [1, 2, 0] 5.) [2, 0, 1] 6.) [2, 1, 0] This approach will use the idea that we notice patterns. Notice how we plant the 0, the 1, then the 2 in the first slot as we go through the sequence. Also, notice how the last element is the array completely reversed. These may not matter but we are just piecing things together right now. Let's formulate a plan. [6, 2, 1, 5, 4, 3, 0] We know to get to this permutation we rooted 6 rooted 2 rooted 1 If you remember back to generating permutations it was all about planting items and then picking from a pool of remaining items. When we plant 1 we have a pool like so [5, 4, 3, 0]. Remember how the last permutation was the original pool reversed? We will look for the longest reversed pool because we know that it is the last permutation for that particular rooting. This is [5, 4, 3, 0] in the example given. This is a maximum suffix after the planted 1. 1 is of interest since this means we have exhausted the possibilities of permutations with 1 rooted where it is since it's suffix following it is strictly decreasing. SO TO GET THE NEXT PERMUTATION WE SWAP 1 AND THE SMALLEST NEXT ELEMENT TO MINIMIZE CHANGE IN TH