Next Arrangement in Order

Medium

List every distinct arrangement of an array's elements and sort the list lexicographically, the way a dictionary orders words: compare the first elements, then the second ones on a tie, and so on. For [1, 2, 3] the order is [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]. Given an array values, return the arrangement that comes next in this order. If values is already the last one, return the first one, that is, the elements sorted ascending. Can you do it with constant extra memory, rearranging the elements right inside values?

Example 1

values=[2, 4, 3, 1] → [3, 1, 2, 4]

The tail 4, 3, 1 is descending. Swap the 2 for the smallest larger value in the tail, 3, and sort the rest (1, 2, 4) ascending: [3, 1, 2, 4].

Example 2

values=[5, 5, 2] → [2, 5, 5]

This is the last arrangement in order, so the array wraps around to the first one: [2, 5, 5].

Example 3

values=[1, 3, 3] → [3, 1, 3]

The arrangements in order are [1, 3, 3], [3, 1, 3], [3, 3, 1], so the next one is [3, 1, 3].

Constraints

1 ≤ len(values) ≤ 100
0 ≤ values[i] ≤ 100

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Two Pointers

Similar problems

Two Boards Holding Water Medium Zero-Sum Triples Medium Triple Sum Nearest the Target Medium Four Numbers to a Target Medium Flags in Three Colors Medium

Input

values=[2, 4, 3, 1]

Expected

[3, 1, 2, 4]

Run checks the first 3 tests in your browser. Submit checks all 38 tests on the server, hidden ones included.