Generate All Distinct Permutations of a List with Duplicate Values
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a list of integers that may contain duplicate values, return every distinct ordering of all of its elements.
### Function Signature
```python
def distinct_permutations(nums: list[int]) -> list[list[int]]:
```
### Rules
- A permutation uses every element of `nums` exactly once, in some order.
- Two permutations are the same if they are equal as sequences of values, even when they come from rearranging equal elements. Each distinct permutation appears exactly once in the result.
- Return the permutations sorted in ascending lexicographic order: compare two permutations element by element, and the first position where they differ decides which comes first.
### Constraints
- `1 <= len(nums) <= 8`
- `-10 <= nums[i] <= 10`
- The result has at most `40320` permutations, reached when all eight elements are distinct.
### Examples
**Example 1**
- Input: `nums = [1, 1, 2]`
- Output: `[[1, 1, 2], [1, 2, 1], [2, 1, 1]]`
- Explanation: Swapping the two `1` values gives the same sequence, so there are three distinct permutations rather than six.
**Example 2**
- Input: `nums = [0, -1, 0]`
- Output: `[[-1, 0, 0], [0, -1, 0], [0, 0, -1]]`
- Explanation: The order of the input does not matter; the output is always in lexicographic order.
**Example 3**
- Input: `nums = [7]`
- Output: `[[7]]`
Overview: Given a list of up to eight integers that may contain duplicates, return every distinct permutation exactly once, sorted in lexicographic order. It tests systematic enumeration, avoiding duplicate results caused by equal values, and producing a deterministic output order.
You are given a list of integers `nums`, which may contain repeated values. Produce every distinct arrangement of all of its elements.
An arrangement places every element of `nums` exactly once, in some order. Two arrangements count as the same when they are equal as sequences of values; rearranging equal elements does not create a new arrangement. Each distinct arrangement must appear exactly once in your result.
**Output order.** Return the arrangements sorted in ascending lexicographic order: compare two arrangements element by element, using numeric comparison, and the first position where they differ decides which one comes first. The first arrangement is therefore `nums` sorted in ascending order, and the last is `nums` sorted in descending order.
Implement `distinct_permutations(nums)`, which returns a list of lists of integers.
**Example 1**
- Input: `nums = [1, 1, 2]`
- Output: `[[1, 1, 2], [1, 2, 1], [2, 1, 1]]`
- Swapping the two `1` values gives the same sequence, so there are three distinct arrangements rather than six.
**Example 2**
- Input: `nums = [0, -1, 0]`
- Output: `[[-1, 0, 0], [0, -1, 0], [0, 0, -1]]`
- The input order does not matter; the output is always in lexicographic order, and `-1` sorts before `0`.
**Example 3**
- Input: `nums = [7]`
- Output: `[[7]]`
**Constraints**
- `1 <= len(nums) <= 8`
- `-10 <= nums[i] <= 10`
- The result has at most `40320` arrangements, reached when all eight elements are distinct.
- Every value fits in a 32-bit signed integer.
Constraints
- 1 <= len(nums) <= 8
- -10 <= nums[i] <= 10
- The result has at most 40320 arrangements (8!), reached when all eight elements are distinct
- Every value fits in a 32-bit signed integer
Examples
Input: ([1, 1, 2],)
Expected Output: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
Input: ([0, -1, 0],)
Expected Output: [[-1, 0, 0], [0, -1, 0], [0, 0, -1]]
Hints
- If you sort the input first, how can you generate arrangements so that they come out already in lexicographic order?
- Generating all n! orderings and removing duplicates afterwards works, but consider a method that never produces the same sequence twice in the first place.
- Given one arrangement, can you compute the smallest arrangement that is strictly larger than it, treating equal values as indistinguishable?