Longest Chain of Pairs

🎯

Longest Chain of Pairs

mediumDPAmazonGoogle

Imagine you have a set of pairs representing tasks with start and end times, and you want to schedule the maximum number of non-overlapping tasks in a chain.

💡 This problem is a variant of the Longest Increasing Subsequence (LIS) but with pairs. Beginners often struggle because it looks like a greedy scheduling problem but requires dynamic programming to handle all cases optimally.

📋

Problem Statement

Given n pairs of numbers where each pair is of the form (a, b) and a < b, find the length of the longest chain which can be formed such that for every pair (c, d) that follows (a, b) in the chain, b < c. Return the length of the longest chain possible.

1 ≤ n ≤ 10^5-10^9 ≤ a < b ≤ 10^9

💡

Example

Input"pairs = [[1,2],[2,3],[3,4]]"

Output2

The longest chain is [1,2] -> [3,4]. The pair [2,3] cannot be chained after [1,2] because 2 is not less than 2.

• All pairs have the same start and end → output is 1
• Pairs are already sorted and non-overlapping → output is n
• Pairs are in descending order → output is 1
• Pairs with negative and positive values → output depends on chaining

🔁

Why DP?

Why greedy fails:

A greedy approach that always picks the next pair with the smallest end that can be chained fails when a locally optimal choice prevents longer chains later. For example, choosing [1,2] then [2,3] greedily misses the longer chain [1,2] then [3,4].

DP state:

dp[i] represents the length of the longest chain ending with the i-th pair after sorting pairs by their first element.

Recurrence:dp[i] = max(1, max(dp[j] + 1 for all j < i if pairs[j][1] < pairs[i][0]))

For each pair i, find all pairs j before i that can chain to i, and take the longest chain length among them plus one for pair i itself.

⚠️

Common Mistakes

Not sorting pairs before DP or greedy

Incorrect chain lengths or logic errors

✅ Always sort pairs by start or end as required before processing

Using greedy approach sorting by start instead of end

Greedy fails to find optimal chain

✅ Sort by end time for greedy to work correctly

Forgetting to check pairs[j][1] < pairs[i][0] in DP

Invalid chains counted, wrong answer

✅ Always check compatibility condition before updating dp

Using recursion without memoization for large inputs

Time limit exceeded or stack overflow

✅ Add memoization or switch to bottom-up DP

Returning dp array max without handling empty input

Runtime error or incorrect result

✅ Check if dp is empty before taking max

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's recursive nature and why naive solutions are inefficient.

Intuition

Try every pair as a potential start and recursively find the longest chain by choosing compatible next pairs.

Algorithm

1. Sort pairs by their first element to have a consistent order.
2. For each pair, recursively find the longest chain starting from it.
3. At each step, try all pairs that can follow the current pair.
4. Return the maximum chain length found.

💡 The recursion tree grows exponentially because each pair can lead to many next pairs, making it hard to track all possibilities.

Recurrence:f(i) = 1 + max(f(j)) for all j > i where pairs[i][1] < pairs[j][0]

</>

Code

from typing import List

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        pairs.sort(key=lambda x: x[0])
        n = len(pairs)

        def dfs(i):
            max_len = 1
            for j in range(i + 1, n):
                if pairs[i][1] < pairs[j][0]:
                    length = 1 + dfs(j)
                    if length > max_len:
                        max_len = length
            return max_len

        max_chain = 0
        for i in range(n):
            current = dfs(i)
            if current > max_chain:
                max_chain = current
        return max_chain

# Driver code
if __name__ == '__main__':
    sol = Solution()
    print(sol.findLongestChain([[1,2],[2,3],[3,4]]))  # Output: 2

Line Notes

pairs.sort(key=lambda x: x[0])Sort pairs to ensure consistent order for chaining

def dfs(i):Define recursive function to find longest chain starting at pair i

for j in range(i + 1, n):Try all pairs after i to find compatible next pairs

if pairs[i][1] < pairs[j][0]:Check if pair j can follow pair i in the chain

length = 1 + dfs(j)Recursively compute chain length including pair j

for i in range(n):Try starting chain from every pair to find global maximum

return max_chainReturn the longest chain length found

import java.util.*;

public class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, Comparator.comparingInt(a -> a[0]));
        int n = pairs.length;

        int maxChain = 0;
        for (int i = 0; i < n; i++) {
            maxChain = Math.max(maxChain, dfs(pairs, i));
        }
        return maxChain;
    }

    private int dfs(int[][] pairs, int i) {
        int maxLen = 1;
        for (int j = i + 1; j < pairs.length; j++) {
            if (pairs[i][1] < pairs[j][0]) {
                int length = 1 + dfs(pairs, j);
                if (length > maxLen) {
                    maxLen = length;
                }
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.findLongestChain(new int[][]{{1,2},{2,3},{3,4}})); // Output: 2
    }
}

Line Notes

Arrays.sort(pairs, Comparator.comparingInt(a -> a[0]))Sort pairs by first element for consistent chaining order

for (int i = 0; i < n; i++)Try starting chain from every pair

private int dfs(int[][] pairs, int i)Recursive method to find longest chain starting at i

if (pairs[i][1] < pairs[j][0])Check if pair j can follow pair i

int length = 1 + dfs(pairs, j)Recursively compute chain length including pair j

return maxLenReturn longest chain length starting at i

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(), [](auto &a, auto &b) { return a[0] < b[0]; });
        int n = pairs.size();
        int maxChain = 0;
        for (int i = 0; i < n; i++) {
            maxChain = max(maxChain, dfs(pairs, i));
        }
        return maxChain;
    }

private:
    int dfs(vector<vector<int>>& pairs, int i) {
        int maxLen = 1;
        for (int j = i + 1; j < pairs.size(); j++) {
            if (pairs[i][1] < pairs[j][0]) {
                int length = 1 + dfs(pairs, j);
                if (length > maxLen) {
                    maxLen = length;
                }
            }
        }
        return maxLen;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> pairs = {{1,2},{2,3},{3,4}};
    cout << sol.findLongestChain(pairs) << endl; // Output: 2
    return 0;
}

Line Notes

sort(pairs.begin(), pairs.end(), [](auto &a, auto &b) { return a[0] < b[0]; })Sort pairs by first element for consistent chaining

for (int i = 0; i < n; i++)Try starting chain from every pair

int dfs(vector<vector<int>>& pairs, int i)Recursive function to find longest chain starting at i

if (pairs[i][1] < pairs[j][0])Check if pair j can follow pair i

int length = 1 + dfs(pairs, j)Recursively compute chain length including pair j

return maxLenReturn longest chain length starting at i

var findLongestChain = function(pairs) {
    pairs.sort((a, b) => a[0] - b[0]);
    const n = pairs.length;

    function dfs(i) {
        let maxLen = 1;
        for (let j = i + 1; j < n; j++) {
            if (pairs[i][1] < pairs[j][0]) {
                const length = 1 + dfs(j);
                if (length > maxLen) {
                    maxLen = length;
                }
            }
        }
        return maxLen;
    }

    let maxChain = 0;
    for (let i = 0; i < n; i++) {
        maxChain = Math.max(maxChain, dfs(i));
    }
    return maxChain;
};

// Test
console.log(findLongestChain([[1,2],[2,3],[3,4]])); // Output: 2

Line Notes

pairs.sort((a, b) => a[0] - b[0])Sort pairs by first element for consistent chaining

function dfs(i)Recursive function to find longest chain starting at i

for (let j = i + 1; j < n; j++)Try all pairs after i for chaining

if (pairs[i][1] < pairs[j][0])Check if pair j can follow pair i

const length = 1 + dfs(j)Recursively compute chain length including pair j

for (let i = 0; i < n; i++)Try starting chain from every pair

return maxChainReturn the longest chain length found

⏱

Complexity

TimeO(n^2)

SpaceO(n) for recursion stack

For each pair, we recursively check all subsequent pairs, leading to O(n^2) calls in worst case.

💡 For n=20, this means up to 400 recursive calls, which grows quickly and becomes impractical for large n.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's recursive structure.

🧠

Top-Down DP with Memoization

💡 Memoization avoids recomputing the same subproblems, drastically improving efficiency over brute force.

Intuition

Store results of longest chains starting at each pair to reuse them instead of recomputing.

Algorithm

1. Sort pairs by their first element.
2. Use a recursive function with a memo dictionary to store results for each index.
3. For each pair, recursively compute the longest chain starting there, caching results.
4. Return the maximum chain length found.

💡 Memoization transforms exponential recursion into polynomial time by caching.

Recurrence:dp[i] = 1 + max(dp[j]) for all j > i where pairs[i][1] < pairs[j][0], else 1

</>

Code

from typing import List

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        pairs.sort(key=lambda x: x[0])
        n = len(pairs)
        memo = {}

        def dfs(i):
            if i in memo:
                return memo[i]
            max_len = 1
            for j in range(i + 1, n):
                if pairs[i][1] < pairs[j][0]:
                    length = 1 + dfs(j)
                    if length > max_len:
                        max_len = length
            memo[i] = max_len
            return max_len

        max_chain = 0
        for i in range(n):
            current = dfs(i)
            if current > max_chain:
                max_chain = current
        return max_chain

# Driver code
if __name__ == '__main__':
    sol = Solution()
    print(sol.findLongestChain([[1,2],[2,3],[3,4]]))  # Output: 2

Line Notes

memo = {}Initialize memo dictionary to cache results

if i in memo:Return cached result to avoid recomputation

memo[i] = max_lenStore computed result for index i

for j in range(i + 1, n):Check all pairs after i for chaining

if pairs[i][1] < pairs[j][0]:Check compatibility for chaining

max_chain = 0Track global maximum chain length

return max_chainReturn longest chain length found

import java.util.*;

public class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, Comparator.comparingInt(a -> a[0]));
        int n = pairs.length;
        Integer[] memo = new Integer[n];

        int maxChain = 0;
        for (int i = 0; i < n; i++) {
            maxChain = Math.max(maxChain, dfs(pairs, i, memo));
        }
        return maxChain;
    }

    private int dfs(int[][] pairs, int i, Integer[] memo) {
        if (memo[i] != null) return memo[i];
        int maxLen = 1;
        for (int j = i + 1; j < pairs.length; j++) {
            if (pairs[i][1] < pairs[j][0]) {
                int length = 1 + dfs(pairs, j, memo);
                if (length > maxLen) {
                    maxLen = length;
                }
            }
        }
        memo[i] = maxLen;
        return maxLen;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.findLongestChain(new int[][]{{1,2},{2,3},{3,4}})); // Output: 2
    }
}

Line Notes

Integer[] memo = new Integer[n]Memo array to cache results for each index

if (memo[i] != null) return memo[i]Return cached result if available

memo[i] = maxLenStore computed longest chain length for i

for (int j = i + 1; j < pairs.length; j++)Check all subsequent pairs for chaining

if (pairs[i][1] < pairs[j][0])Check if pairs are compatible

maxChain = Math.max(maxChain, dfs(pairs, i, memo))Update global maximum chain length

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(), [](auto &a, auto &b) { return a[0] < b[0]; });
        int n = pairs.size();
        vector<int> memo(n, -1);
        int maxChain = 0;
        for (int i = 0; i < n; i++) {
            maxChain = max(maxChain, dfs(pairs, i, memo));
        }
        return maxChain;
    }

private:
    int dfs(vector<vector<int>>& pairs, int i, vector<int>& memo) {
        if (memo[i] != -1) return memo[i];
        int maxLen = 1;
        for (int j = i + 1; j < pairs.size(); j++) {
            if (pairs[i][1] < pairs[j][0]) {
                int length = 1 + dfs(pairs, j, memo);
                if (length > maxLen) {
                    maxLen = length;
                }
            }
        }
        memo[i] = maxLen;
        return maxLen;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> pairs = {{1,2},{2,3},{3,4}};
    cout << sol.findLongestChain(pairs) << endl; // Output: 2
    return 0;
}

Line Notes

vector<int> memo(n, -1)Initialize memo vector with -1 to indicate uncomputed states

if (memo[i] != -1) return memo[i]Return cached result if computed

memo[i] = maxLenCache computed longest chain length for i

for (int j = i + 1; j < pairs.size(); j++)Check all subsequent pairs for chaining

if (pairs[i][1] < pairs[j][0])Check compatibility of pairs

maxChain = max(maxChain, dfs(pairs, i, memo))Update global maximum chain length

var findLongestChain = function(pairs) {
    pairs.sort((a, b) => a[0] - b[0]);
    const n = pairs.length;
    const memo = new Array(n).fill(-1);

    function dfs(i) {
        if (memo[i] !== -1) return memo[i];
        let maxLen = 1;
        for (let j = i + 1; j < n; j++) {
            if (pairs[i][1] < pairs[j][0]) {
                const length = 1 + dfs(j);
                if (length > maxLen) {
                    maxLen = length;
                }
            }
        }
        memo[i] = maxLen;
        return maxLen;
    }

    let maxChain = 0;
    for (let i = 0; i < n; i++) {
        maxChain = Math.max(maxChain, dfs(i));
    }
    return maxChain;
};

// Test
console.log(findLongestChain([[1,2],[2,3],[3,4]])); // Output: 2

Line Notes

const memo = new Array(n).fill(-1)Initialize memo array with -1 for uncomputed states

if (memo[i] !== -1) return memo[i]Return cached result if available

memo[i] = maxLenCache computed longest chain length for i

for (let j = i + 1; j < n; j++)Check all subsequent pairs for chaining

if (pairs[i][1] < pairs[j][0])Check if pairs are compatible

maxChain = Math.max(maxChain, dfs(i))Update global maximum chain length

⏱

Complexity

TimeO(n^2)

SpaceO(n) for memo and recursion stack

Memoization avoids repeated work but still checks pairs in nested loops, leading to O(n^2) time.

💡 For n=1000, this means about 1,000,000 operations, which is feasible but slow for very large inputs.

Interview Verdict: Accepted

This approach is efficient enough for moderate input sizes and demonstrates DP optimization.

🧠

Bottom-Up DP (Tabulation)

💡 Tabulation builds the solution iteratively, which is often easier to debug and understand than recursion.

Intuition

Sort pairs and for each pair, find the longest chain ending there by checking all previous compatible pairs.

Algorithm

1. Sort pairs by their first element.
2. Initialize a dp array with 1s, since each pair alone forms a chain of length 1.
3. For each pair i from left to right, check all pairs j before i.
4. If pairs[j][1] < pairs[i][0], update dp[i] = max(dp[i], dp[j] + 1).
5. Return the maximum value in dp.

💡 This approach explicitly builds up solutions for smaller subproblems to solve larger ones.

Recurrence:dp[i] = max(1, max(dp[j] + 1 for all j < i if pairs[j][1] < pairs[i][0]))

</>

Code

from typing import List

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        pairs.sort(key=lambda x: x[0])
        n = len(pairs)
        dp = [1] * n

        for i in range(n):
            for j in range(i):
                if pairs[j][1] < pairs[i][0]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp) if dp else 0

# Driver code
if __name__ == '__main__':
    sol = Solution()
    print(sol.findLongestChain([[1,2],[2,3],[3,4]]))  # Output: 2

Line Notes

dp = [1] * nInitialize dp with 1 since each pair alone forms a chain

for i in range(n)Iterate over pairs to compute longest chain ending at i

for j in range(i)Check all previous pairs j before i

if pairs[j][1] < pairs[i][0]Check if pair j can chain to pair i

dp[i] = max(dp[i], dp[j] + 1)Update dp[i] if chaining through j yields longer chain

return max(dp) if dp else 0Return the maximum chain length found

import java.util.*;

public class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, Comparator.comparingInt(a -> a[0]));
        int n = pairs.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (pairs[j][1] < pairs[i][0]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int maxChain = 0;
        for (int length : dp) {
            maxChain = Math.max(maxChain, length);
        }
        return maxChain;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.findLongestChain(new int[][]{{1,2},{2,3},{3,4}})); // Output: 2
    }
}

Line Notes

int[] dp = new int[n]DP array to store longest chain ending at each pair

Arrays.fill(dp, 1)Initialize dp with 1 since each pair alone forms a chain

for (int i = 0; i < n; i++)Iterate over pairs to compute dp[i]

for (int j = 0; j < i; j++)Check all previous pairs j before i

if (pairs[j][1] < pairs[i][0])Check if pairs are compatible for chaining

dp[i] = Math.max(dp[i], dp[j] + 1)Update dp[i] if chaining through j is better

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(), [](auto &a, auto &b) { return a[0] < b[0]; });
        int n = pairs.size();
        vector<int> dp(n, 1);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (pairs[j][1] < pairs[i][0]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }

        return *max_element(dp.begin(), dp.end());
    }
};

int main() {
    Solution sol;
    vector<vector<int>> pairs = {{1,2},{2,3},{3,4}};
    cout << sol.findLongestChain(pairs) << endl; // Output: 2
    return 0;
}

Line Notes

vector<int> dp(n, 1)Initialize dp with 1 for each pair

for (int i = 0; i < n; i++)Compute longest chain ending at i

for (int j = 0; j < i; j++)Check all previous pairs j before i

if (pairs[j][1] < pairs[i][0])Check compatibility for chaining

dp[i] = max(dp[i], dp[j] + 1)Update dp[i] if chaining through j is longer

return *max_element(dp.begin(), dp.end())Return maximum chain length found

var findLongestChain = function(pairs) {
    pairs.sort((a, b) => a[0] - b[0]);
    const n = pairs.length;
    const dp = new Array(n).fill(1);

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (pairs[j][1] < pairs[i][0]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    return Math.max(...dp);
};

// Test
console.log(findLongestChain([[1,2],[2,3],[3,4]])); // Output: 2

Line Notes

const dp = new Array(n).fill(1)Initialize dp array with 1 for each pair

for (let i = 0; i < n; i++)Compute longest chain ending at i

for (let j = 0; j < i; j++)Check all previous pairs j before i

if (pairs[j][1] < pairs[i][0])Check if pairs can chain

dp[i] = Math.max(dp[i], dp[j] + 1)Update dp[i] if chaining through j is longer

return Math.max(...dp)Return maximum chain length found

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Nested loops check all pairs, leading to quadratic time; dp array uses linear space.

💡 For n=1000, about 1 million operations, which is acceptable in interviews.

Interview Verdict: Accepted

This is the standard DP solution for this problem and is efficient enough for most inputs.

🧠

Greedy Approach (Sorting by End Time)

💡 A greedy approach sorts pairs by their end time and greedily picks pairs to form the longest chain, achieving optimal solution efficiently.

Intuition

Always pick the pair with the smallest end time that can be chained next to maximize future options.

Algorithm

1. Sort pairs by their second element (end time).
2. Initialize current end to negative infinity and count to 0.
3. Iterate over pairs; if a pair's start is greater than current end, include it and update current end.
4. Return the count of pairs included.

💡 This approach leverages the problem's structure to avoid DP and achieve linear time after sorting.

Recurrence:Not applicable (greedy, no DP recurrence)

</>

Code

from typing import List

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        pairs.sort(key=lambda x: x[1])
        current_end = float('-inf')
        count = 0
        for pair in pairs:
            if pair[0] > current_end:
                count += 1
                current_end = pair[1]
        return count

# Driver code
if __name__ == '__main__':
    sol = Solution()
    print(sol.findLongestChain([[1,2],[2,3],[3,4]]))  # Output: 2

Line Notes

pairs.sort(key=lambda x: x[1])Sort pairs by their end time to pick earliest finishing pairs first

current_end = float('-inf')Initialize current end to smallest possible to allow first pair

if pair[0] > current_endCheck if current pair can be chained after last chosen pair

count += 1Include current pair in the chain

current_end = pair[1]Update current end to end time of chosen pair

return countReturn total number of pairs in longest chain

import java.util.*;

public class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, Comparator.comparingInt(a -> a[1]));
        int currentEnd = Integer.MIN_VALUE;
        int count = 0;
        for (int[] pair : pairs) {
            if (pair[0] > currentEnd) {
                count++;
                currentEnd = pair[1];
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.findLongestChain(new int[][]{{1,2},{2,3},{3,4}})); // Output: 2
    }
}

Line Notes

Arrays.sort(pairs, Comparator.comparingInt(a -> a[1]))Sort pairs by end time for greedy selection

int currentEnd = Integer.MIN_VALUEInitialize current end to smallest integer

if (pair[0] > currentEnd)Check if pair can be chained after last chosen pair

count++Include pair in chain

currentEnd = pair[1]Update current end to chosen pair's end time

return countReturn length of longest chain

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(), [](auto &a, auto &b) { return a[1] < b[1]; });
        int currentEnd = INT_MIN;
        int count = 0;
        for (auto &pair : pairs) {
            if (pair[0] > currentEnd) {
                count++;
                currentEnd = pair[1];
            }
        }
        return count;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> pairs = {{1,2},{2,3},{3,4}};
    cout << sol.findLongestChain(pairs) << endl; // Output: 2
    return 0;
}

Line Notes

sort(pairs.begin(), pairs.end(), [](auto &a, auto &b) { return a[1] < b[1]; })Sort pairs by end time for greedy approach

int currentEnd = INT_MINInitialize current end to smallest integer

if (pair[0] > currentEnd)Check if pair can be chained after last chosen pair

count++Include pair in chain

currentEnd = pair[1]Update current end to chosen pair's end time

return countReturn length of longest chain

var findLongestChain = function(pairs) {
    pairs.sort((a, b) => a[1] - b[1]);
    let currentEnd = Number.NEGATIVE_INFINITY;
    let count = 0;
    for (const pair of pairs) {
        if (pair[0] > currentEnd) {
            count++;
            currentEnd = pair[1];
        }
    }
    return count;
};

// Test
console.log(findLongestChain([[1,2],[2,3],[3,4]])); // Output: 2

Line Notes

pairs.sort((a, b) => a[1] - b[1])Sort pairs by end time for greedy selection

let currentEnd = Number.NEGATIVE_INFINITYInitialize current end to smallest possible

if (pair[0] > currentEnd)Check if pair can be chained after last chosen pair

count++Include pair in chain

currentEnd = pair[1]Update current end to chosen pair's end time

return countReturn length of longest chain

⏱

Complexity

TimeO(n log n)

SpaceO(1)

Sorting takes O(n log n), and a single pass selects pairs greedily in O(n).

💡 For n=100000, sorting is the main cost, but the greedy selection is very fast.

Interview Verdict: Accepted

This is the most efficient and elegant solution, often preferred in interviews once DP is understood.

📊

All Approaches - One-Glance Tradeoffs

💡 Greedy is best for coding in interviews after understanding DP; memoization and tabulation are good for explaining DP concepts.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2) exponential recursion	O(n) recursion stack	Yes	Yes	Mention only - never code
2. Top-Down DP with Memoization	O(n^2)	O(n) memo + recursion stack	Possible but less than brute force	Yes	Explain to optimize brute force
3. Bottom-Up DP (Tabulation)	O(n^2)	O(n)	No	Yes	Standard DP solution to code
4. Greedy Approach	O(n log n)	O(1)	No	Yes, with minor modifications	Optimal solution to code if allowed

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know when to apply each during interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Explain the brute force recursive approach to show understanding.Step 3: Introduce memoization to optimize recursion.Step 4: Present bottom-up DP as a clean iterative solution.Step 5: Finally, discuss the greedy approach as the optimal solution.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of DP, ability to optimize naive solutions, and knowledge of greedy algorithms for interval problems.

Common Follow-ups

• What if pairs are not sorted? → Sort first to simplify chaining.
• Can you reconstruct the actual chain? → Use parent pointers in DP.
• What if pairs overlap partially? → Same approach applies with careful comparisons.
• Can greedy always solve this? → Yes, for this problem due to interval scheduling properties.

💡 These follow-ups test deeper understanding and ability to extend solutions.

🔍

Pattern Recognition

When to Use

1) Problem involves pairs or intervals, 2) Need longest chain or sequence, 3) Compatibility condition between pairs, 4) Overlapping subproblems or scheduling nature.

Signature Phrases

longest chainpairs (a, b) with a < bb < c for chaining

NOT This Pattern When

Interval Scheduling Maximization without chain length, or problems requiring sum maximization instead of length.

Similar Problems

Longest Increasing Subsequence - similar DP structureMaximum Length of Pair Chain - same problem on LeetCodeRussian Doll Envelopes - similar nesting and DP

Practice

1. You are given a 2D grid of integers and need to find the length of the longest strictly increasing path moving only up, down, left, or right. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach that always moves to the neighbor with the largest value

B. Topological sort based dynamic programming processing cells in ascending order of their values

C. Simple DFS from each cell without memoization

D. Breadth-first search layer by layer from the smallest values

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the longest strictly increasing path in a matrix, which can be modeled as a directed graph where edges go from smaller to larger values.

2. Step 2: Identify suitable algorithm

   Topological sort based DP processes nodes in ascending order, ensuring all dependencies are resolved before updating dp values, guaranteeing optimal substructure and avoiding recomputation.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Topological sort ensures correct order for DP updates [OK]

Hint: Longest increasing path -> topological sort DP [OK]

Common Mistakes:

• Assuming greedy always works
• Using DFS without memoization causing TLE
• Using BFS layer by layer ignoring value order

2. You are given a list of envelopes, each with a width and height. You want to find the maximum number of envelopes you can nest inside each other such that each envelope fits strictly inside the next one by both width and height. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic programming with nested loops checking all pairs of envelopes for nesting conditions

B. Greedy algorithm that sorts envelopes by width and picks the tallest envelope at each step

C. Sort envelopes by width ascending and height descending, then find the Longest Increasing Subsequence (LIS) on heights using binary search

D. Use a graph and find the longest path by topological sorting

Solution

1. Step 1: Understand problem constraints

   The problem requires strict nesting by both width and height, so sorting by width ascending and height descending ensures envelopes with the same width do not interfere with LIS on height.

2. Step 2: Recognize LIS pattern on heights

   After sorting, the problem reduces to finding the LIS on heights, which can be done optimally with binary search for O(n log n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting by width ascending and height descending + LIS on heights -> optimal solution [OK]

Hint: Sort width asc, height desc, then LIS on height [OK]

Common Mistakes:

• Sorting both width and height ascending causes incorrect LIS
• Using greedy height selection without sorting
• Applying graph longest path without sorting

3. What is the time complexity of the optimal DP solution that uses a list of hash maps to count arithmetic subsequences by their differences for an input array of length n?

medium

A. O(n * 2^n) due to enumerating all subsequences

B. O(n^2) because of nested loops over pairs and constant-time hashmap operations

C. O(n^3) because for each pair we scan all previous elements

D. O(n^2 * log n) due to sorting differences in hash maps

Solution

1. Step 1: Identify loops in the DP solution

   The code has two nested loops over indices i and j, each up to n, resulting in O(n²) iterations.

2. Step 2: Analyze hashmap operations

   Hash map insertions and lookups are amortized O(1), so total complexity is O(n²).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP with hash maps runs in quadratic time, not exponential or cubic [OK]

Hint: Two nested loops with O(1) hashmap ops -> O(n²) time [OK]

Common Mistakes:

• Confusing with brute force exponential time
• Assuming cubic due to triple nested loops
• Thinking sorting is involved

4. What is the time complexity of the topological sort based DP solution for the longest increasing path in an m x n matrix?

medium

A. O(m * n * log(m * n))

B. O(m * n^2)

C. O(m * n * 4^{m*n})

D. O(m * n)

Solution

1. Step 1: Identify sorting cost

   Sorting all m*n cells by their values costs O(m*n*log(m*n)).

2. Step 2: Analyze DP updates

   Each cell checks up to 4 neighbors, so DP updates cost O(m*n) total.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting dominates, so complexity is O(m*n*log(m*n)) [OK]

Hint: Sorting cells dominates complexity [OK]

Common Mistakes:

• Assuming DP is O(m*n) ignoring sorting
• Confusing exponential brute force with DP
• Ignoring log factor from sorting

5. Suppose the problem is modified so that elements can be reused multiple times in subsequences (i.e., subsequences are multisets, not strictly increasing indices). Which change to the DP approach correctly counts all arithmetic subsequences under this new constraint?

hard

A. Keep the same DP but allow j to be equal to i to reuse elements

B. Use a DP that counts subsequences by difference without restricting j < i, allowing repeated indices

C. Modify DP to consider all pairs (i, j) with i ≤ j and update counts accordingly

D. Switch to a combinatorial formula since DP no longer applies

Solution

1. Step 1: Understand reuse means indices can repeat or be equal

   Original DP requires j < i to ensure strictly increasing indices; reuse breaks this.

2. Step 2: Modify DP loops to allow i ≤ j and update counts accordingly

   Allowing i ≤ j and updating dp[i][diff] with dp[j][diff] + 1 counts subsequences with repeated elements correctly.

3. Step 3: Reject naive reuse of original DP or combinatorial formulas

   Original DP with j < i fails; combinatorial formulas are not straightforward here.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Allowing i ≤ j and updating counts handles reuse correctly [OK]

Hint: Reuse requires relaxing j < i to i ≤ j in DP loops [OK]

Common Mistakes:

• Trying to reuse original DP without index relaxation
• Assuming combinatorial formula suffices
• Allowing j = i without updating counts properly