Skip to content

Validate Sequence of Numbers

Level: L3-L5 Topics: Graphs, Topological Sort, Cycle Detection, Directed Graphs

Problem Statement

A sequence of numbers was written on a blackboard. Several friends each looked at the blackboard and remembered a partial subsequence — a subset of the numbers in the order they appeared. However, none of the friends necessarily saw the complete sequence.

Given all the partial subsequences that the friends reported, determine whether there exists a valid consensus sequence — a single sequence that is consistent with every friend's observation. If a valid consensus exists, reconstruct it. If no valid consensus exists (the observations contradict each other), report that it is impossible.

Background & Constraints

  • Each friend's observation is an ordered list of numbers representing a subsequence they remember.
  • A consensus sequence must contain all numbers mentioned by any friend, in an order that respects every friend's reported ordering.
  • Numbers may appear in multiple friends' observations.
  • If friend A reports [1, 2, 4] and friend B reports [2, 7, 4], the consensus must have 1 before 2, 2 before 4, and 2 before 7, and 7 before 4.
  • The consensus is impossible if the constraints form a contradiction (a cycle).

Examples

Example 1: Valid Consensus

Friend 1 saw: [1, 2, 4]
Friend 2 saw: [2, 7, 4]
Friend 3 saw: [1, 15, 8]

Constraints derived:
1 -> 2 -> 4
2 -> 7 -> 4
1 -> 15 -> 8

One valid consensus: [1, 2, 7, 15, 4, 8]
(Other valid orderings may also exist.)

Example 2: Contradiction

Friend 1 saw: [1, 2, 3]
Friend 2 saw: [3, 1]

Constraints: 1 before 2, 2 before 3, and 3 before 1.
This creates a cycle: 1 -> 2 -> 3 -> 1
No valid consensus exists.

Example 3: Simple Case

Friend 1 saw: [5, 10]
Friend 2 saw: [5, 7, 10]

Valid consensus: [5, 7, 10]

Hints & Common Pitfalls

  • Key insight: Build a directed graph where an edge from A to B means "A must appear before B." Each friend's observation [a1, a2, ..., ak] creates edges a1->a2, a2->a3, ..., a(k-1)->ak.
  • Cycle detection determines whether a valid consensus exists. If the directed graph has a cycle, the observations are contradictory.
  • Topological sort of the directed graph gives a valid consensus ordering (if one exists). Any valid topological order satisfies all the constraints.
  • Common mistake: Only checking adjacent pairs from different friends' lists without building the full constraint graph.
  • Common mistake: Assuming there is only one valid consensus. There may be many — you just need to find one or prove none exists.
  • If the same number appears at different positions in different friends' observations, make sure to reconcile those positions through the graph edges.

Follow-Up Questions

  1. What is the time complexity of your solution in terms of the total number of elements across all observations?
  2. If multiple valid consensus sequences exist, how would you enumerate all of them?
  3. What if friends can make mistakes, and you want to find the consensus that satisfies the maximum number of constraints? How does this change the problem complexity?
  4. How would you handle duplicate numbers (the same number appearing more than once in the original sequence)?
  5. Can you solve this in a streaming fashion, processing one friend's observation at a time?