The O(n) Club: Next Permutation – Because Arrays Get Bored Too

The O(n) Club: Next Permutation – Because Arrays Get Bored Too

⚡ TL;DR

Given an array, your job is to rearrange it into the next lexicographically greater permutation (basically, its next ‘word’ in dictionary order, if it could spell). No possible ‘next’? Shuffle it back to the smallest order (sort ascending). Here’s how you make Java do it in record time:

// Given int[] nums
int i = nums.length - 2;
while(i >= 0 && nums[i] >= nums[i+1]) i--;
if(i >= 0) {
    int j = nums.length - 1;
    while(nums[j] <= nums[i]) j--;
    int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp;
}
int left = i+1, right = nums.length-1;
while(left < right) {
    int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp;
    left++; right--;
}

🧠 How Devs Usually Mess This Up

Let’s get this out of the way: if your first instinct is “just generate all permutations and sort them,” congratulations, you have invented slow-motion misery. That’s O(n!) — i.e., suited for arrays of size less than your coffee mug. Oh, and sorting the suffix instead of reversing it? That’s like emptying the dishwasher to find one spoon. Your CPU will file a complaint.

🔍 What’s Actually Going On

Imagine your array is a band lineup. To get the ‘next concert schedule,’ you:

• Walk backwards until some star (nums[i]) says, “I’d rather swap with the next hotter star.” (First i so that nums[i] < nums[i+1]). That’s your pivot.
• If all you hear is grumbling (array in full descending order), you’ve hit the last show: reverse to reset.
• Otherwise, find the celeb just bigger than nums[i] (the next-perkier rightmost member) and swap ‘em.
• Finally, give the suffix after i a makeover: reverse it (don’t sort!). It’s already the worst order, so one flip makes it best.

It’s less “permutation magic” and more “fix your lineup with two swaps and call it innovation.”

🛠️ PseudoCode

• Step 1: Find the last rising edge.
  int i = nums.length - 2; while (i >= 0 && nums[i] >= nums[i + 1]) i--;
  (Seeking the last hopeful number.)
• Step 2: If not found (i == -1), reverse the whole array.
  (Already maxed out, time to reboot.)
• Step 3: Otherwise, find smallest number to right that’s bigger than nums[i]; swap.
  int j = nums.length - 1; while (nums[j] <= nums[i]) j--; swap(nums, i, j);
• Step 4: Reverse suffix (everything right of i).
  reverse(nums, i + 1, nums.length - 1);

💻 The Code

public class NextPermutation {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;
        if (i >= 0) {
            int j = nums.length - 1;
            while (nums[j] <= nums[i]) j--;
            swap(nums, i, j);
        }
        reverse(nums, i + 1, nums.length - 1);
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp;
    }
    private void reverse(int[] nums, int start, int end) {
        while (start < end) swap(nums, start++, end--);
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Sorting the suffix: Don’t do it. It’s already descending – just reverse and call it a day.
• Missing the edge case: all elements same, or size 2? Still works (with maybe more yawns).
• For [3,2,1], you get [1,2,3]. For [1,1,5], you get [1,5,1]. No recursion, no stress, no late-night debugging.
• O(n) time. O(1) space. Harder to get wrong than a coffee order, if you follow the steps.

🧠 Interviewer Brain-Tattoo

“Don’t bubble-sort your array’s future—reverse it and move on with your life.”