Katkat
Back

Generate All Distinct Permutations of a List with Duplicate Values

LinkedInSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

Given a list of integers that may contain duplicate values, return every distinct ordering of all of its elements.

Function Signature

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]]