Technical Concepts

Appearance

Patience Sorting ​

Introduction ​

Patience Sorting is an elegant sorting algorithm inspired by the card game "Patience" (also known as Solitaire). It works by distributing elements into organized piles following a simple rule, then merging those piles back together. Beyond sorting, its most famous application is finding the Longest Increasing Subsequence (LIS) of a sequence — a classic problem that appears frequently in coding interviews and competitive programming.

The Card Game Analogy ​

Imagine you're playing a simplified version of Solitaire. You're dealt cards one at a time from a deck, and you must place each card onto a pile following these rules:

  1. You can place a card on any existing pile whose top card is greater than or equal to the card you're placing.
  2. If no such pile exists, you start a new pile to the right.
  3. When multiple piles are valid, you always choose the leftmost valid pile (the one whose top card is the smallest among valid options).

Once all cards are dealt, the number of piles you end up with equals the length of the Longest Increasing Subsequence. That's the magic of Patience Sorting.

Core Concepts ​

How the Piles Form ​

Let's walk through an example with the sequence [7, 2, 8, 1, 3, 4, 10, 6, 9, 5].

StepCardActionPiles (top cards shown)
17New pile[7]
22Place on pile 1 (7 ≥ 2)[2]
38New pile (no top ≥ 8)[2] [8]
41Place on pile 1 (2 ≥ 1)[1] [8]
53Place on pile 2 (8 ≥ 3)[1] [3]
64New pile (no top ≥ 4... wait, nope)[1] [3] → 3 < 4, so new pile → [1] [3] [4]
710New pile[1] [3] [4] [10]
86Place on pile 4 (10 ≥ 6)[1] [3] [4] [6]
99New pile (no top ≥ 9... 6 < 9)Wait — we need a pile whose top is ≥ 9. Only nothing qualifies → new pile
105Place on pile 4 (6 ≥ 5)[1] [3] [4] [5] [9]

We end up with 5 piles, meaning the Longest Increasing Subsequence has length 5 (e.g., [1, 3, 4, 6, 9]).

Wait — let me redo this more carefully since finding the leftmost pile is key:

Why "Leftmost Valid Pile"? ​

Choosing the leftmost valid pile is equivalent to performing a binary search on the top cards of the piles. Since the top cards of all piles are always in increasing order (a key invariant!), we can use binary search to find the correct pile in O(log n) time.

This invariant holds because: if you place a smaller card on a pile, that pile's top gets smaller, and any new pile you create must have a larger top than all existing piles.

Complexity ​

OperationTime ComplexitySpace Complexity
Dealing into pilesO(n log n)O(n)
Finding LIS lengthO(n log n)O(n)
Finding actual LISO(n log n)O(n)
Full sort (with merge)O(n log n)O(n)

The O(n log n) comes from: n cards × O(log n) binary search per card.

Problems Addressed ​

1. Longest Increasing Subsequence (LIS) ​

This is the flagship problem for Patience Sorting. Given a sequence of numbers, find the longest subsequence where each element is strictly greater than the previous one.

Example: In [10, 9, 2, 5, 3, 7, 101, 18], the LIS is [2, 3, 7, 101] with length 4.

A naive dynamic programming approach solves this in O(n²). Patience Sorting brings it down to O(n log n).

2. Sorting with Natural Runs ​

Patience Sorting excels when the input is nearly sorted or has many ascending runs. The algorithm naturally detects and leverages existing order in the data.

3. Minimum Number of Decreasing Subsequences ​

By Dilworth's theorem, the minimum number of decreasing subsequences needed to cover a sequence equals the length of the longest increasing subsequence. The piles in Patience Sorting represent exactly these decreasing subsequences.

Implementation ​

Finding LIS Length Using Patience Sorting ​

This is the most common interview application. We only track the top cards of each pile.

javascript
/**
 * Finds the length of the Longest Increasing Subsequence
 * using the Patience Sorting technique.
 * 
 * We maintain an array of "pile tops" and use binary search
 * to find where each new element goes.
 * 
 * @param {number[]} nums - Input array
 * @returns {number} Length of the LIS
 */
function lisLength(nums) {
    if (nums.length === 0) return 0;
    
    // pileTops[i] = the top card (smallest value) on pile i
    const pileTops = [];
    
    for (const num of nums) {
        // Binary search for the leftmost pile whose top >= num
        let lo = 0;
        let hi = pileTops.length;
        
        while (lo < hi) {
            const mid = Math.floor((lo + hi) / 2);
            if (pileTops[mid] < num) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        
        if (lo === pileTops.length) {
            // No valid pile found — create a new one
            pileTops.push(num);
        } else {
            // Place on the leftmost valid pile
            pileTops[lo] = num;
        }
    }
    
    // Number of piles = LIS length
    return pileTops.length;
}

// --- Demo ---
console.log(lisLength([10, 9, 2, 5, 3, 7, 101, 18])); // 4
console.log(lisLength([0, 1, 0, 3, 2, 3]));            // 4
console.log(lisLength([7, 7, 7, 7, 7]));               // 1
console.log(lisLength([3, 1, 4, 1, 5, 9, 2, 6]));      // 4

Recovering the Actual LIS (Not Just the Length) ​

To reconstruct the actual subsequence, we need to maintain back-pointers. Each element remembers which element came before it in the subsequence.

javascript
/**
 * Finds the actual Longest Increasing Subsequence,
 * not just its length. Uses back-pointers to reconstruct.
 * 
 * @param {number[]} nums - Input array
 * @returns {number[]} The longest increasing subsequence
 */
function findLIS(nums) {
    if (nums.length === 0) return [];
    
    const n = nums.length;
    
    // pileTops[i] stores the INDEX of the top element on pile i
    const pileTops = [];
    
    // parent[i] = index of the element that comes before nums[i] in the LIS
    const parent = new Array(n).fill(-1);
    
    for (let i = 0; i < n; i++) {
        // Binary search for leftmost pile whose top value >= nums[i]
        let lo = 0;
        let hi = pileTops.length;
        
        while (lo < hi) {
            const mid = Math.floor((lo + hi) / 2);
            if (nums[pileTops[mid]] < nums[i]) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        
        // Set back-pointer: the element on the pile to the LEFT
        // is the previous element in our increasing subsequence
        if (lo > 0) {
            parent[i] = pileTops[lo - 1];
        }
        
        if (lo === pileTops.length) {
            pileTops.push(i);
        } else {
            pileTops[lo] = i;
        }
    }
    
    // Reconstruct the LIS by following back-pointers
    const lis = [];
    let idx = pileTops[pileTops.length - 1];
    
    while (idx !== -1) {
        lis.push(nums[idx]);
        idx = parent[idx];
    }
    
    return lis.reverse();
}

// --- Demo ---
console.log(findLIS([10, 9, 2, 5, 3, 7, 101, 18])); 
// [2, 3, 7, 18] or [2, 5, 7, 18] or [2, 3, 7, 101]

console.log(findLIS([3, 1, 4, 1, 5, 9, 2, 6]));
// [1, 4, 5, 6] or [1, 2, 5, 6] etc.

console.log(findLIS([0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]));
// [0, 2, 6, 9, 11, 15] — length 6

Full Patience Sort (Sorting an Array) ​

For the actual sorting application, we deal cards into piles, then perform a k-way merge (similar to merge sort's merge step) using a min-heap.

javascript
/**
 * A MinHeap implementation for the k-way merge phase.
 */
class MinHeap {
    constructor(compareFn) {
        this.data = [];
        this.compare = compareFn || ((a, b) => a - b);
    }
    
    push(val) {
        this.data.push(val);
        this._bubbleUp(this.data.length - 1);
    }
    
    pop() {
        const top = this.data[0];
        const last = this.data.pop();
        if (this.data.length > 0) {
            this.data[0] = last;
            this._sinkDown(0);
        }
        return top;
    }
    
    size() { return this.data.length; }
    
    _bubbleUp(i) {
        while (i > 0) {
            const parent = Math.floor((i - 1) / 2);
            if (this.compare(this.data[i], this.data[parent]) < 0) {
                [this.data[i], this.data[parent]] = [this.data[parent], this.data[i]];
                i = parent;
            } else break;
        }
    }
    
    _sinkDown(i) {
        const n = this.data.length;
        while (true) {
            let smallest = i;
            const left = 2 * i + 1;
            const right = 2 * i + 2;
            if (left < n && this.compare(this.data[left], this.data[smallest]) < 0)
                smallest = left;
            if (right < n && this.compare(this.data[right], this.data[smallest]) < 0)
                smallest = right;
            if (smallest !== i) {
                [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
                i = smallest;
            } else break;
        }
    }
}

/**
 * Full Patience Sort: deals into piles, then merges using a min-heap.
 * 
 * @param {number[]} arr - Input array
 * @returns {number[]} Sorted array
 */
function patienceSort(arr) {
    if (arr.length <= 1) return [...arr];
    
    // Phase 1: Deal into piles
    const piles = []; // Each pile is an array (stack), last element = top
    
    for (const num of arr) {
        // Binary search for leftmost pile whose top >= num
        let lo = 0;
        let hi = piles.length;
        
        while (lo < hi) {
            const mid = Math.floor((lo + hi) / 2);
            if (piles[mid][piles[mid].length - 1] < num) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        
        if (lo === piles.length) {
            piles.push([num]);
        } else {
            piles[lo].push(num);
        }
    }
    
    // Phase 2: k-way merge using a min-heap
    // Each heap entry: { value, pileIndex }
    const heap = new MinHeap((a, b) => a.value - b.value);
    
    // Initialize heap with the top of each pile
    for (let i = 0; i < piles.length; i++) {
        heap.push({ value: piles[i].pop(), pileIndex: i });
    }
    
    const sorted = [];
    
    while (heap.size() > 0) {
        const { value, pileIndex } = heap.pop();
        sorted.push(value);
        
        // If this pile still has cards, push the next one
        if (piles[pileIndex].length > 0) {
            heap.push({
                value: piles[pileIndex].pop(),
                pileIndex: pileIndex
            });
        }
    }
    
    return sorted;
}

// --- Demo ---
console.log(patienceSort([7, 2, 8, 1, 3, 4, 10, 6, 9, 5]));
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

console.log(patienceSort([5, 3, 1, 4, 2]));
// [1, 2, 3, 4, 5]

Handling Non-Strict (Non-Decreasing) LIS ​

Sometimes the problem asks for the longest non-decreasing subsequence (allowing duplicates). We just change the binary search condition:

javascript
/**
 * LIS length allowing equal consecutive elements (non-decreasing).
 * The only change: use <= instead of < in binary search.
 */
function lisLengthNonDecreasing(nums) {
    const pileTops = [];
    
    for (const num of nums) {
        let lo = 0;
        let hi = pileTops.length;
        
        while (lo < hi) {
            const mid = Math.floor((lo + hi) / 2);
            // Changed: strictly less becomes less-or-equal
            if (pileTops[mid] <= num) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        
        if (lo === pileTops.length) {
            pileTops.push(num);
        } else {
            pileTops[lo] = num;
        }
    }
    
    return pileTops.length;
}

// --- Demo ---
console.log(lisLengthNonDecreasing([1, 3, 3, 3, 5])); // 5 (all elements)
console.log(lisLengthNonDecreasing([7, 7, 7, 7]));     // 4

Visual Walkthrough: Pile Formation ​

Let's trace through [3, 1, 4, 1, 5, 9, 2, 6] step by step:

Final pile tops: [1, 2, 5, 6] — and that's exactly a valid LIS! (Though note: the pile tops array isn't always a valid LIS itself; the length is always correct.)

Comparing Approaches to LIS ​

ApproachTimeSpaceCan Recover LIS?
Brute ForceO(2^n)O(n)Yes
DP (classic)O(n²)O(n)Yes
Patience SortO(n log n)O(n)Yes (with back-pointers)

The O(n²) DP for Comparison ​

To appreciate why Patience Sorting is elegant, here's the classic DP approach:

javascript
/**
 * Classic O(n²) DP for LIS — shown for comparison.
 * For each position, we look at ALL previous positions.
 */
function lisDPQuadratic(nums) {
    const n = nums.length;
    if (n === 0) return 0;
    
    // dp[i] = length of LIS ending at index i
    const dp = new Array(n).fill(1);
    
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    
    return Math.max(...dp);
}

console.log(lisDPQuadratic([10, 9, 2, 5, 3, 7, 101, 18])); // 4

For n = 100,000, the DP takes ~10 billion operations. Patience Sorting does it in ~1.7 million. That's the difference between waiting minutes and getting results instantly.

Connection to Dilworth's Theorem ​

Dilworth's Theorem is a beautiful result from combinatorics:

In any finite partially ordered set, the maximum number of elements in any antichain equals the minimum number of chains needed to partition the set.

Translated to sequences:

  • Chain = increasing subsequence
  • Antichain = decreasing subsequence
  • The longest increasing subsequence length = minimum number of decreasing subsequences to cover the entire sequence

Each pile in Patience Sorting is a decreasing subsequence, and the number of piles equals the LIS length. This is Dilworth's theorem in action!

Best Practices ​

  1. Use the pileTops-only version for LIS length: If you just need the length and not the actual subsequence, the simpler version without back-pointers is cleaner and faster in practice.

  2. Mind the strict vs. non-strict distinction: For strictly increasing, use < in binary search; for non-decreasing (allowing duplicates), use <=. Getting this wrong is the #1 interview mistake.

  3. Remember pileTops isn't the actual LIS: A common misconception — the pileTops array at the end has the right length but may not be a valid subsequence of the original array. Use back-pointers to reconstruct the actual LIS.

  4. Use built-in binary search when available: In interviews, you can write your own, but in production code, leverage standard library bisect functions for correctness.

  5. Consider Patience Sort for nearly-sorted data: If your data has long ascending runs, Patience Sort produces fewer piles and the merge phase is cheaper, making it competitive with Timsort.

  6. Adapt for 2D problems carefully: Problems like the "Russian Doll Envelopes" (LIS in 2D) require sorting by one dimension and applying Patience Sorting on the other — but the second dimension must be in reverse order to avoid counting same-width envelopes.

  7. Keep the invariant in mind: The pile tops are always sorted in increasing order. If you ever get confused about the algorithm, return to this invariant — it's the key to everything.

  • Binary Search: The core technique that makes Patience Sorting O(n log n). Search for it as a standalone topic if you're not comfortable with it.
  • Merge Sort: The k-way merge phase of full Patience Sort uses the same merging concept.
  • Min-Heap / Priority Queue: Used in the merge phase — the Heaps article in this repository covers this in depth.
  • Dynamic Programming: The O(n²) LIS solution is a classic DP problem. Understanding both approaches is essential.
  • Binary Indexed Trees (Fenwick Trees): Can also solve LIS in O(n log n) with a different approach — worth comparing.
  • Segment Trees: Another alternative for LIS and related range-query problems.

Tests and Challenges ​

Practice these problems to solidify your understanding of Patience Sorting and LIS:

LeetCode ​

ProblemDifficultyNotes
300. Longest Increasing SubsequenceMediumThe classic — implement both O(n²) DP and O(n log n) Patience
354. Russian Doll EnvelopesHard2D LIS — sort by width, then LIS on height (reversed)
673. Number of Longest Increasing SubsequencesMediumCount how many LIS exist — extends the basic idea
334. Increasing Triplet SubsequenceMediumSimplified LIS — just need length ≥ 3
1964. Find the Longest Valid Obstacle Course at Each PositionHardNon-decreasing subsequence variant

HackerRank ​

Tips for Interviews ​

  • Start by explaining the card game analogy — interviewers love it when you can explain an algorithm through an intuitive story
  • Code the LIS-length-only version first, then offer to extend it with back-pointers if asked
  • Always mention the time complexity improvement: O(n²) → O(n log n)
  • If asked "why does this work?", explain the pile tops invariant (always sorted in increasing order)