Skip to content
Hello Python

Build a Unique Assignment

Practice ExerciseIntermediateMediumConstraint SatisfactionArrayHash Set

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement smallest_unique_assignment(options). options[i] lists allowed integer values for position i. Return the lexicographically smallest assignment using no value twice, or [] if none exists.

Starter code

def smallest_unique_assignment(options):
    pass
Test cases

requires-backtrack

{
  "args": [
    [
      [
        1,
        2
      ],
      [
        1
      ],
      [
        2,
        3
      ]
    ]
  ]
}

Expected: [2,1,3]

impossible-assignment

{
  "args": [
    [
      [
        1
      ],
      [
        1
      ]
    ]
  ]
}

Expected: []

Wizard outline
  1. Step 1: Choose an unused value

    Build one position while respecting the uniqueness set. Incremental constraint checks prune invalid partial assignments immediately.

  2. Step 2: Undo failed choices

    Backtrack when a locally valid choice blocks a later position. A failed suffix means the current choice must be removed before trying its sibling candidate.

  3. Step 3: Guarantee the smallest solution

    Return the lexicographically smallest complete assignment or empty. Depth-first search over sorted candidates visits complete assignments in lexicographic order.

Footguns and prerequisites
  • Forgetting to remove a choice during backtracking leaks state into sibling branches.
  • Returning the first input-order answer is not lexicographically deterministic.
  • recursion and backtracking
Reviewed references
Recommended approach and implementation

Depth-first assign sorted candidate values, pruning used values and undoing both assignment and constraint state after failure.

Why it works: Each branch contains only unique partial assignments. Backtracking enumerates every legal candidate sequence, and sorted traversal makes the first complete sequence lexicographically smallest; if none completes, no valid assignment exists.

def smallest_unique_assignment(options):
    assignment = []
    used = set()
    def search(position):
        if position == len(options):
            return True
        for value in sorted(options[position]):
            if value in used:
                continue
            used.add(value)
            assignment.append(value)
            if search(position + 1):
                return True
            assignment.pop()
            used.remove(value)
        return False
    return assignment if search(0) else []