Skip to main content

40. Next Permutation

mediumAsked at Salesforce

Compute the next lexicographic permutation of an array in place. Salesforce uses this to test in-place array manipulation with a non-obvious algorithm.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses this as a 'do you know the next-permutation algorithm?' filter.
  • LeetCode Discuss (2025)— Rarely solved cold; Salesforce tests preparation.

Problem

A permutation of an array of integers is an arrangement of its members into a sequence or linear order. The next permutation of an array of integers is the next lexicographically greater permutation of its integer. If such an arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order). Modify nums in-place.

Constraints

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

Examples

Example 1

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

Example 2

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

Example 3

Input
nums = [1,1,5]
Output
[1,5,1]

Approaches

1. Generate all permutations and find next

Enumerate all permutations, sort, find the next one greater than current.

Time
O(n! * n)
Space
O(n!)
function nextPermutation(nums) {
  // pseudocode: generate all permutations, sort, find next.
  // not feasible for n > 10
}

Tradeoff: Factorial. Doesn't scale. Salesforce wants O(n).

2. Find pivot from right, swap, reverse suffix

1. From the right, find first i where nums[i] < nums[i+1]. 2. From the right, find first j > i where nums[j] > nums[i]. 3. Swap nums[i] and nums[j]. 4. Reverse the suffix after i.

Time
O(n)
Space
O(1)
function 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]];
  }
  // reverse suffix from i+1
  let l = i + 1, r = nums.length - 1;
  while (l < r) { [nums[l], nums[r]] = [nums[r], nums[l]]; l++; r--; }
}

Tradeoff: O(n) time, O(1) space. The pivot/swap/reverse trio is the textbook algorithm — knowing it on the spot is the signal.

Salesforce-specific tips

Salesforce flags this as a 'preparation check' — they want to see if you can derive or recall the pivot/swap/reverse algorithm. Bonus signal: explain WHY reverse works as the final step (the suffix after the swap is in descending order, so reversing turns it into ascending — the smallest tail).

Common mistakes

  • Forgetting the i >= 0 check — array sorted descending gives i = -1, and we should reverse the whole array.
  • Reversing before swapping — wrong order.
  • Searching j with j < i — must be j > i.

Follow-up questions

An interviewer at Salesforce may pivot to one of these next:

  • Previous Permutation (mirror algorithm).
  • Permutations (LC 46) — enumerate all.
  • Kth Permutation Sequence (LC 60).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is the suffix always descending after the pivot?

Because the pivot is the LAST i where nums[i] < nums[i+1]. Everything to the right of i is non-increasing (descending or equal).

Why does the algorithm produce the NEXT permutation?

The pivot is the leftmost position we can increment. Swapping with the smallest larger value in the suffix gives the minimum increment. Reversing the suffix makes it the smallest possible tail.

Practice these live with InterviewChamp.AI

Drill Next Permutation and other Salesforce interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →