The next permutation of an array

You are in a Meta interview and the interviewer pulls up a shared coding environment. "Given an array of integers, rearrange it to its next lexicographic permutation. If the array is already the largest permutation, wrap around to the smallest one. Do it in-place with constant extra memory." This problem, also known as Next Permutation on other platforms, is a favorite at companies like Meta, Google, and Apple because it combines array manipulation with a non-obvious algorithmic insight that separates strong candidates from the rest.

TL;DR

Scan right to left to find the first element smaller than its right neighbor (the "pivot"). Then find the smallest element to the right of the pivot that is still larger than it (the "successor"), swap them, and reverse the suffix after the pivot position. If no pivot exists, the array is fully descending, so reverse the whole thing to wrap around. This runs in O(n) time and O(1) space.

Why This Problem Matters

The next permutation problem shows up frequently in interviews at Meta (39 reported occurrences), J.P. Morgan, Google, and Apple. It tests your ability to spot a multi-step pattern in array manipulation and implement it cleanly under the constraint of constant extra memory. Once you understand the three-step approach, the code writes itself. But getting to that understanding requires thinking carefully about what makes one permutation "next" in lexicographic order.

Lexicographic Order: The Foundation

Before we jump into the algorithm, let's make sure we have a clear mental model of lexicographic ordering. Think of it like dictionary order extended to numbers. For the array [1, 2, 3], all six permutations in lexicographic order are:

Each permutation is the smallest possible rearrangement that is still larger than the previous one. Our job is to go from any permutation to the one immediately after it in this sequence.

Prefer a different language? Jump to solutions in other languages.

Understanding the Problem

Given: An integer array nums Task: Rearrange it to the next lexicographically greater permutation, in-place Edge case: If already the largest permutation, wrap to the smallest (ascending order) Constraint: Use only O(1) extra memory

nextPermutation([1, 2, 3]) => [1, 3, 2]
nextPermutation([3, 2, 1]) => [1, 2, 3]
nextPermutation([1, 1, 5]) => [1, 5, 1]

Edge Cases to Consider

1. Single element: [1] has no other permutation, return as-is
2. Fully descending: [3, 2, 1] wraps around to [1, 2, 3]
3. Duplicates: [1, 1, 5] still works correctly with the algorithm
4. Already ascending suffix: Only the last two elements need swapping, like [1, 2, 3] becoming [1, 3, 2]

The Three-Step Algorithm

Here is the key observation: if the suffix of the array (reading from right to left) is entirely non-increasing, there is no way to make a larger permutation by only rearranging that suffix. We need to involve at least one element to the left of the suffix.

This leads to a clean three-step process.

Step 1: Find the Pivot

Scan from right to left and find the first index i where nums[i] is strictly less than nums[i + 1]. This element is the "pivot." Everything to its right is in non-increasing order.

Let's trace through [2, 3, 6, 5, 4, 1]:

Reading from the right: 1 ≤ 4 ≤ 5 ≤ 6 forms a non-increasing suffix. But nums[1] = 3 is less than nums[2] = 6, so i = 1 is our pivot.

Step 2: Find the Successor and Swap

Now scan the suffix from right to left to find the smallest element that is strictly greater than the pivot. Swap them.

Scanning from the right: 1 is not greater than 3, but 4 is. So we swap nums[1] = 3 with nums[4] = 4, giving us [2, 4, 6, 5, 3, 1].

Why does this work? We need the digit at the pivot position to increase by the smallest possible amount. The successor is exactly that smallest-possible replacement.

Step 3: Reverse the Suffix

After the swap, the suffix is still in non-increasing order. To get the smallest possible permutation with the new pivot value, we reverse the suffix to make it non-decreasing.

Reversing [6, 5, 3, 1] gives [1, 3, 5, 6], and the final result is [2, 4, 1, 3, 5, 6].

The Wrap-Around Case

When the entire array is in descending order, no pivot exists. The algorithm handles this naturally: i reaches -1, we skip the swap, and reverse the entire array.

Implementation

Here is the Java solution with helper methods for swap and reverse:

public class Solution {
  public int[] nextPermutation(int[] nums) {
    // Step 1: Find the pivot - first decreasing element from the right
    int i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
      i--;
    }

    // Step 2: If pivot exists, find successor and swap
    if (i >= 0) {
      int j = nums.length - 1;
      while (nums[j] <= nums[i]) {
        j--;
      }
      swap(nums, i, j);
    }

    // Step 3: Reverse the suffix after the pivot
    reverse(nums, i + 1);
    return nums;
  }

  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 = nums.length - 1;
    while (start < end) {
      swap(nums, start, end);
      start++;
      end--;
    }
  }
}

Let's walk through a more complex example to build confidence. Consider [1, 5, 8, 5, 1, 3, 4, 6, 7]:

Scanning from right: 7 > 6, and at index 7, nums[7] = 6 is less than nums[8] = 7. So the pivot is at index 7. The successor is nums[8] = 7 (first value from right that exceeds 6). After swapping: [1, 5, 8, 5, 1, 3, 4, 7, 6]. The suffix after the pivot is just [6] (a single element), so no reversal changes anything. The final answer is [1, 5, 8, 5, 1, 3, 4, 7, 6].

Why the Suffix Stays Non-Increasing After the Swap

This is a detail worth understanding. Before the swap, the suffix is non-increasing: ... a >= b >= c >= .... When we swap the pivot with the successor, the successor was chosen as the rightmost element greater than the pivot. Since the suffix is non-increasing, the element immediately to the right of the successor is less than or equal to the successor, and the element to the left of the successor is greater than or equal to the successor. After the swap, the pivot (which is smaller than the old successor) takes the successor's place, preserving the non-increasing property.

Complexity Analysis

Time Complexity: O(n)

Each of the three steps scans at most the full array once:

• Finding the pivot: at most n-1 comparisons
• Finding the successor: at most n-1 comparisons
• Reversing the suffix: at most n/2 swaps

All three are linear, so the total is O(n).

Space Complexity: O(1)

We use only a few integer variables (i, j, temp). The reversal and swap happen in-place. No auxiliary arrays or data structures are needed.

Common Pitfalls

1. Using > instead of >= when finding the pivot: The condition must be nums[i] >= nums[i + 1] (not strict greater-than) to handle duplicates correctly. With strict >, the algorithm would stop at equal elements and produce incorrect results for inputs like [1, 5, 1].

2. Forgetting to reverse the suffix: After swapping, many candidates assume the result is complete. Without the reversal step, the suffix remains in descending order instead of ascending, giving a permutation that is too large.

3. Off-by-one in the reverse range: The reversal starts at i + 1, not i. The pivot position already has its correct value after the swap.

4. Not handling the wrap-around case: When i ends up at -1, the suffix reversal starting at i + 1 = 0 naturally reverses the entire array. Some candidates add an unnecessary special case here.

Interview Tips

When you encounter this problem in an interview:

1. Start with small examples. Trace through [1, 2, 3] and [3, 2, 1] by hand to build intuition about what "next" means in lexicographic order.

2. Explain the three-step process before coding. Interviewers want to see that you understand the algorithm, not just memorize it. Walk through why each step is necessary.

3. Mention the non-increasing suffix property. This is the key insight. Explain why the suffix to the right of the pivot must be non-increasing, and why that property makes the reversal correct.

4. Test with duplicates. Run through [1, 1, 5] to show the algorithm handles equal elements. This demonstrates attention to detail.

5. Discuss alternatives if asked. You could generate all permutations and find the next one (O(n! * n) time), or sort the suffix instead of reversing it (O(n log n) time). The three-step approach is optimal at O(n).

Key Takeaways

• The next permutation algorithm uses a three-step process: find the pivot, swap with its successor, and reverse the suffix. Each step has a clear purpose.
• The pivot is the rightmost element that is smaller than its right neighbor. Everything to the right of the pivot is in non-increasing order, meaning no larger permutation is possible by rearranging only that suffix.
• Reversing the suffix after the swap converts it from non-increasing to non-decreasing order, producing the smallest possible arrangement. This is faster than sorting because the suffix is already ordered.
• The algorithm handles duplicates correctly because it uses >= (not >) comparisons. It handles the wrap-around case naturally by reversing the entire array when no pivot is found.
• Time is O(n) and space is O(1), making this the optimal solution for in-place next permutation computation.

Solutions in Other Languages

Python

class Solution:
    def next_permutation(self, nums):
        n = len(nums)
        if n <= 1:
            return nums

        # Step 1: Find pivot
        k = n - 2
        while k >= 0 and nums[k] >= nums[k + 1]:
            k -= 1

        if k == -1:
            nums.reverse()
            return nums

        # Step 2: Find successor and swap
        l = n - 1
        while nums[k] >= nums[l]:
            l -= 1
        nums[k], nums[l] = nums[l], nums[k]

        # Step 3: Reverse suffix
        nums[k + 1:] = reversed(nums[k + 1:])
        return nums

JavaScript

class Solution {
  nextPermutation(nums) {
    let i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
      i--;
    }

    if (i >= 0) {
      let j = nums.length - 1;
      while (nums[j] <= nums[i]) {
        j--;
      }
      [nums[i], nums[j]] = [nums[j], nums[i]];
    }

    let left = i + 1;
    let right = nums.length - 1;
    while (left < right) {
      [nums[left], nums[right]] = [nums[right], nums[left]];
      left++;
      right--;
    }

    return nums;
  }
}

TypeScript

class Solution {
  nextPermutation(nums: number[]): number[] {
    let i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
      i--;
    }

    if (i >= 0) {
      let j = nums.length - 1;
      while (nums[j] <= nums[i]) {
        j--;
      }
      [nums[i], nums[j]] = [nums[j], nums[i]];
    }

    let left = i + 1;
    let right = nums.length - 1;
    while (left < right) {
      [nums[left], nums[right]] = [nums[right], nums[left]];
      left++;
      right--;
    }

    return nums;
  }
}

C++

class Solution {
public:
    std::vector<int> nextPermutation(std::vector<int> &nums) {
        int n = nums.size();
        int i = n - 2;

        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        if (i >= 0) {
            int j = n - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            std::swap(nums[i], nums[j]);
        }

        std::reverse(nums.begin() + i + 1, nums.end());
        return nums;
    }
};

Scala

class Solution {
  def nextPermutation(nums: Array[Int]): Array[Int] = {
    def swap(i: Int, j: Int): Unit = {
      val temp = nums(i)
      nums(i) = nums(j)
      nums(j) = temp
    }

    def reverse(start: Int): Unit = {
      var i = start
      var j = nums.length - 1
      while (i < j) {
        swap(i, j)
        i += 1
        j -= 1
      }
    }

    if (nums.length <= 1) return nums

    var i = nums.length - 2
    while (i >= 0 && nums(i) >= nums(i + 1)) {
      i -= 1
    }

    if (i >= 0) {
      var j = nums.length - 1
      while (nums(j) <= nums(i)) {
        j -= 1
      }
      swap(i, j)
    }

    reverse(i + 1)
    nums
  }
}

Kotlin

class Solution {
  fun nextPermutation(nums: IntArray): IntArray {
    var i = nums.lastIndex - 1
    while (i >= 0 && nums[i] >= nums[i + 1]) {
      i--
    }
    if (i >= 0) {
      var j = nums.lastIndex
      while (nums[j] <= nums[i]) {
        j--
      }
      nums[i] = nums[j].also { nums[j] = nums[i] }
    }
    var left = i + 1
    var right = nums.lastIndex
    while (left < right) {
      nums[left] = nums[right].also { nums[right] = nums[left] }
      left++
      right--
    }
    return nums
  }
}

Swift

class Solution {
    func nextPermutation(_ nums: [Int]) -> [Int] {
        var nums = nums
        var i = nums.count - 2
        while i >= 0 && nums[i] >= nums[i + 1] {
            i -= 1
        }
        if i >= 0 {
            var j = nums.count - 1
            while nums[j] <= nums[i] {
                j -= 1
            }
            let temp = nums[i]
            nums[i] = nums[j]
            nums[j] = temp
        }
        var left = i + 1
        var right = nums.count - 1
        while left < right {
            let temp = nums[left]
            nums[left] = nums[right]
            nums[right] = temp
            left += 1
            right -= 1
        }
        return nums
    }
}

Ruby

class Solution
  def next_permutation(nums)
    i = nums.length - 2
    while i >= 0 && nums[i] >= nums[i + 1]
      i -= 1
    end
    if i >= 0
      j = nums.length - 1
      while nums[j] <= nums[i]
        j -= 1
      end
      nums[i], nums[j] = nums[j], nums[i]
    end
    left = i + 1
    right = nums.length - 1
    while left < right
      nums[left], nums[right] = nums[right], nums[left]
      left += 1
      right -= 1
    end
    nums
  end
end

Rust

impl Solution {
    pub fn next_permutation(&self, mut nums: Vec<i32>) -> Vec<i32> {
        let mut i = nums.len() as i32 - 2;
        while i >= 0 && nums[i as usize] >= nums[(i + 1) as usize] {
            i -= 1;
        }
        if i >= 0 {
            let mut j = nums.len() as i32 - 1;
            while nums[j as usize] <= nums[i as usize] {
                j -= 1;
            }
            nums.swap(i as usize, j as usize);
        }
        nums[(i + 1) as usize..].reverse();
        nums
    }
}

Dart

class Solution {
  List<int> nextPermutation(List<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;
    int right = nums.length - 1;
    while (left < right) {
      int temp = nums[left];
      nums[left] = nums[right];
      nums[right] = temp;
      left++;
      right--;
    }
    return nums;
  }
}

C#

public class Solution {
    public int[] 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--;
            }
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        int left = i + 1;
        int right = nums.Length - 1;
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
        return nums;
    }
}

PHP

class Solution {
    public function nextPermutation(array $nums): array {
        $i = count($nums) - 2;
        while ($i >= 0 && $nums[$i] >= $nums[$i + 1]) {
            $i--;
        }
        if ($i >= 0) {
            $j = count($nums) - 1;
            while ($nums[$j] <= $nums[$i]) {
                $j--;
            }
            $temp = $nums[$i];
            $nums[$i] = $nums[$j];
            $nums[$j] = $temp;
        }
        $left = $i + 1;
        $right = count($nums) - 1;
        while ($left < $right) {
            $temp = $nums[$left];
            $nums[$left] = $nums[$right];
            $nums[$right] = $temp;
            $left++;
            $right--;
        }
        return $nums;
    }
}

Practice Makes Perfect

The next permutation algorithm is a building block for several related problems. Once you have this pattern down, try these:

• Permutations: Generate all permutations of an array (backtracking approach)
• Permutation Sequence: Find the kth permutation without generating all of them
• Previous Permutation: Reverse the logic to find the immediately preceding arrangement

Remember, consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Whether you are targeting Meta, Google, or your next dream role, mastering patterns like this will set you apart.