# Rigorous Math proof for equivalence of Uniqueness property and Pair property

• Re: [Simple Solution : one-pass](using only array (C++ 92ms)
@jeffery To translate this into rigorous math statement:

Given a finite sequence `{a[n]}` and a finitely set of finite sequences `{sub[k][n]}`, where each `{sub[k][*]}`is a subsequence of `{a[n]}`. Prove that the following properties are equivalent:

• Uniqueness property: there does not exist another permutation `{a'[n]}` of `{a[n]}` such that each `{sub[k][*]}`is also a subsequence of the permutated `{a'[n]}`.
• Pair property: every adjacent pair `a[i], a[i+1]` shows up in some subsequence `{sub[k][*]}`.

Proof: Both derivation directions can be proved by contradiction.
Pair property=>Uniqueness property: Suppose we have a permutated `{a'[n]}` to be the super sequence of each `{sub[k][*]}`. Since it is permutated, there must exist some adjacent pair `a[i], a[i+1]` from `{a[n]}`such that `a[i+1]`comes before `a[i]`in `{a'[n]}`. But we know the pair `a[i], a[i+1]` shows up in some `{sub[k][*]}`, so this `{sub[k][*]}`cannot be a subsequence of `{a'[n]}`.

Uniqueness property=>Pair property. Suppose there exists some adjacent pair `a[i], a[i+1]` from `{a[n]}`which does not show up in any `{sub[k][*]}`. Then we can define `{a'[n]}` to be same as `{a[n]}`except that only `a[i], a[i+1]` swapped. Note that any other `a[k]` (`k!=i, k!=i+1`) still has the same relative order in `{a'[n]}`compared with `{a[n]}`, so each `{sub[k][*]}`must also be a subsequence for `{a'[n]}`, and this violates the uniqueness property.

Proof is complete.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.