What is the brute force approach and complexity for Sequence Reconstruction?

Try every order of 1..n; keep those where all sequences fit; accept only one that equals nums with time complexity O(n! · S) and space complexity O(n · n!).

What is the optimal approach and complexity for Sequence Reconstruction?

Arrows from neighbouring pairs; Kahn must have exactly one free value each step and match nums with optimal time complexity O(n + S · log S) and space complexity O(n + S).

How do you identify the pattern for Sequence Reconstruction?

Look for key signals in the prompt: "every sequence is a subsequence" indicates Each sequence gives order facts between neighbouring values, so build the graph from them.; "the only list" indicates Kahn's queue must never hold two values, or the order is not forced.; "nums is a permutation of 1..n" indicates Every value must be placed. A missing value or a cycle shows up as an incomplete order..

Sequence Reconstruction

Medium·LeetCode #444 Premium Pro OnlySlight Variation

LeetCode

Problem Statement

You get nums, a list that holds each value from 1 to n exactly once (so it is a permutation of 1..n). You also get sequences, a list of short lists of values.

A list fits when every sequence appears inside it as a subsequence: its values show up in the same order, though not necessarily next to each other.

Return true only when nums is the only list of length n that fits all the sequences. Return false otherwise. That includes the case where several lists fit, and the case where nums itself does not fit.

Input

nums: a permutation of 1..n. sequences: a list of lists of values, each value between 1 and n.

Output

true if nums is the only list that fits every sequence, otherwise false.

Example 1

Input: nums = [1, 2, 3], sequences = [[1, 2], [2, 3]]

Output: true

1 comes before 2, and 2 comes before 3. Only the list 1, 2, 3 fits.

Example 2

Input: nums = [1, 2, 3], sequences = [[1, 2], [1, 3]]

Output: false

2 and 3 can swap. Both [1, 2, 3] and [1, 3, 2] fit, so nums is not the only one.

Example 3

Input: nums = [4, 1, 5, 2, 6, 3], sequences = [[5, 2, 6, 3], [4, 1, 5, 2]]

Output: true

The neighbouring pairs chain together as 4 → 1 → 5 → 2 → 6 → 3. That chain is the only list that fits.

Example 4

Input: nums = [1, 2], sequences = [[1, 2], [2, 1]]

Output: false

The two sequences contradict each other: 1 must come before 2 and 2 before 1. No list fits.

Constraints

• nums is a permutation of the values 1 to n, where n = nums.length.
• Every value in sequences is between 1 and n.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“every sequence is a subsequence”

→ Each sequence gives order facts between neighbouring values, so build the graph from them.

“the only list”

→ Kahn's queue must never hold two values, or the order is not forced.

“nums is a permutation of 1..n”

→ Every value must be placed. A missing value or a cycle shows up as an incomplete order.

Approach Complexity Ladder

Brute Force — count every list that fitsO(n! · S)O(n · n!)

Try every order of 1..n; keep those where all sequences fit; accept only one that equals nums

Optimal — Kahn with exactly one free valueO(n + S · log S)O(n + S)

Arrows from neighbouring pairs; Kahn must have exactly one free value each step and match nums

Brute Force Intuition

Any list that fits must be an order of the values 1..n. Try all of them. Keep each order in which every sequence is a subsequence. Return true only when exactly one order is kept and it equals nums.

Recognition rule for this sub-pattern:

The graph is hidden — derive edges from comparisons (adjacent words, sequences), then topo-sort.

Remember this · Topological Sort

Trigger

Prerequisites, dependencies, build order, "can all courses be finished?", ordering letters from sorted words.

Think

Is this a directed graph where some things must happen before others?

Key question

Which nodes currently have in-degree 0?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Topological Sort translate into production architectures and low-level memory mechanics.

LLD Practice

Task Scheduler & Workflow Orchestrator

Resolving DAG build pipelines and asynchronous task dependency resolution.

Explore Track

C++ Internals

Static vs Global Linkage & Init Order Fiasco

Why compilers resolve static global variables as a DAG to prevent runtime crashes.

Explore Track

Alien Dictionary All Tasks Scheduling Orders