Unique Ordering Verification (Medium) — Practice with Code Visualizer

You are given a proposed ordering represented as an integer array ordering of length n, containing a permutation of integers from 1 to n. You are also provided with a 2D integer array constraints, where each constraints[i] represents a partial ordering that must be preserved as a subsequence within any valid complete ordering.

Your task is to determine whether ordering is the unique shortest complete ordering that satisfies all the given constraints. A complete ordering is considered valid if every constraint array appears as a subsequence within it.

Specifically, return true if and only if:

The ordering is a valid complete ordering (all constraints are subsequences of ordering).
The ordering is the shortest possible complete ordering.
There is no other valid shortest complete ordering besides ordering.

If multiple distinct shortest orderings can satisfy all constraints, or if ordering is not the shortest valid ordering, return false.

Key Concepts:

A subsequence is a sequence derived from another by deleting some (or no) elements without changing the relative order of remaining elements.
A complete ordering contains all elements and respects all constraint relationships.
The shortest complete ordering uses exactly n elements with no unnecessary additions.

Two valid shortest orderings exist: [1,2,3] and [1,3,2]. Both satisfy all constraints. Constraint [1,2] is a subsequence of [1,2,3] (positions 0,1) and [1,3,2] (positions 0,2). Constraint [1,3] is a subsequence of [1,2,3] (positions 0,2) and [1,3,2] (positions 0,1). Since the ordering is not unique, we return false.

The shortest valid ordering that contains [1,2] is simply [1,2] itself. Since [1,2,3] is longer than necessary, the given ordering is not the shortest possible, so we return false.

The only valid shortest ordering is [1,2,3]. Constraint [1,2] forces 1 before 2. Constraint [1,3] forces 1 before 3. Constraint [2,3] forces 2 before 3. Together, these uniquely determine the ordering as 1 → 2 → 3. No other ordering of length 3 satisfies all constraints, so we return true.