Meta·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Meta SWE coding round, got a next permutation problem and had to do it in-place with O(1) space. Pretty classic but the details trip you up if you haven't drilled it recently.

Questions Asked (1)

Given an integer array, modify it in-place to produce the next lexicographically greater permutation. If the array is already the largest permutation, rearrange it into the smallest (ascending) order. Must run in O(n) time with O(1) extra space.

Algorithms & Data Structures

Author's notes

I knew the algorithm from somewhere but blanked on the exact steps mid-explanation.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by explaining the three-step algorithm: find the pivot (first decreasing element from the right), swap it with the smallest larger element to its right, then reverse the suffix to get the next permutation. If no pivot exists, reverse the entire array to get the smallest permutation. Emphasize that this achieves O(n) time and O(1) space by modifying the array in-place.

Pro tip: Mention that this is the exact algorithm used in C++'s std::next_permutation and Python's itertools.permutations, showing you understand real-world implementations. Also, clarify that the reverse step is crucial because the suffix is already in non-increasing order, so reversing it yields the smallest possible arrangement.

1. Find the Pivot

Traverse the array from right to left to find the first element that is smaller than its right neighbor. This element is the pivot. If no such element exists, the array is in descending order, so reverse the entire array and return.

2. Find the Successor

From the right, find the first element that is greater than the pivot. This element is the smallest element greater than the pivot in the suffix (since the suffix is non-increasing).

3. Swap Pivot and Successor

Swap the pivot with the successor. This ensures the next permutation is lexicographically greater.

4. Reverse the Suffix

Reverse the subarray to the right of the pivot's original position. Since the suffix was non-increasing, reversing it makes it non-decreasing, which is the smallest possible arrangement for that suffix.

5. Handle Edge Case

If no pivot was found in step 1, reverse the entire array to get the smallest permutation (ascending order).

Key Points to Mention

Time complexity: O(n) because each step involves at most one pass through the array.
Space complexity: O(1) because all modifications are done in-place with only a few variables.
The suffix after the pivot is always in non-increasing order, which is why we can find the successor by scanning from the right and why reversing yields the smallest arrangement.
Edge cases: array of length 0 or 1, array already in descending order (largest permutation), array with duplicates.
The algorithm is stable and works with duplicate elements because we look for the first element greater than the pivot, not greater or equal.
This is the standard algorithm used in libraries like C++'s std::next_permutation.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.