Russian Doll Envelopes

Problem

You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope’s width and height.

Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

Examples

Example 1:

1
2
3


Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is `3` ([2,3] => [5,4] => [6,7]).

Example 2:

1
2


Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1

Constraints

1 <= envelopes.length <= 10^5
envelopes[i].length == 2
1 <= wi, hi <= 10^5

Solution

Method 1 - Sort by Width and Use DP Like in LIS on Height

Algo

Arrange the envelopes by width in increasing order.
With widths sorted, the problem simplifies to finding the longest increasing subsequence (LIS) based on heights.
Now, apply the LIS algorithm to the heights.

Key point:

Because widths are already sorted, we only need to focus on the heights for the LIS step.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        if (n == 0) return 0;
        sort(envelopes.begin(), envelopes.end());
        vector<int> dp(n, 1);
        int ans = 1;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (envelopes[i][0] > envelopes[j][0] &&
                    envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
                ans = max(ans, dp[i]);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


import "sort"

type Solution struct{}

func (Solution) MaxEnvelopes(envelopes [][]int) int {
    n := len(envelopes)
    if n == 0 {
        return 0
    }
    sort.Slice(envelopes, func(i, j int) bool {
        if envelopes[i][0] == envelopes[j][0] {
            return envelopes[i][1] < envelopes[j][1]
        }
        return envelopes[i][0] < envelopes[j][0]
    })
    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }
    ans := 1
    for i := 1; i < n; i++ {
        for j := 0; j < i; j++ {
            if envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1] {
                if dp[i] < dp[j]+1 {
                    dp[i] = dp[j] + 1
                }
            }
            if ans < dp[i] {
                ans = dp[i]
            }
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
	public int maxEnvelopes(int[][] envelopes) {
		int n = envelopes.length;
		if (n == 0) return 0;
		Arrays.sort(envelopes, (a, b) -> a[0] - b[0]);
		int[] dp = new int[n + 1];
		Arrays.fill(dp, 1);
		int ans = 1;
		for (int i = 1; i<n; ++i) {
			for (int j = 0; j<i; ++j) {
				if (envelopes[i][0] > envelopes[j][0] &&
					envelopes[i][1] > envelopes[j][1]) {
					dp[i] = Math.max(dp[i], 1 + dp[j]);
				}
				ans = Math.max(ans, dp[i]);
			}
		}
		return ans;
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
    fun maxEnvelopes(envelopes: Array<IntArray>): Int {
        val n = envelopes.size
        if (n == 0) return 0
        envelopes.sortWith(compareBy({ it[0] }, { it[1] }))
        val dp = IntArray(n) { 1 }
        var ans = 1
        for (i in 1 until n) {
            for (j in 0 until i) {
                if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = maxOf(dp[i], dp[j] + 1)
                }
                ans = maxOf(ans, dp[i])
            }
        }
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


from typing import List

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        n = len(envelopes)
        if n == 0:
            return 0
        envelopes.sort()
        dp = [1] * n
        ans = 1
        for i in range(1, n):
            for j in range(i):
                if envelopes[i][0] > envelopes[j][0] and envelopes[i][1] > envelopes[j][1]:
                    dp[i] = max(dp[i], dp[j] + 1)
                ans = max(ans, dp[i])
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


impl Solution {
    pub fn max_envelopes(mut envelopes: Vec<Vec<i32>>) -> i32 {
        let n = envelopes.len();
        if n == 0 { return 0; }
        envelopes.sort();
        let mut dp = vec![1; n];
        let mut ans = 1;
        for i in 1..n {
            for j in 0..i {
                if envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1] {
                    dp[i] = dp[i].max(dp[j] + 1);
                }
                ans = ans.max(dp[i]);
            }
        }
        ans
    }
}

Complexity

⏰ Time complexity: O(n log n) + O(n^2) = O(n log n), and may result in TLE.
🧺 Space complexity: O(n)

Method 2 - Sort by Width and Height and Do Binary Search on Height

Instead of O(n^2), we can switch to O(n log n) solution to find LIS, which we have already seen here: Longest Increasing Subsequence LIS.

Algorithm

Sort envelopes in ascending order of width
- If width are equal then sort height in decreasing order. Because when width are same, most remaining envelopes can fit in the biggest envelope of same width, i.e. biggest height.
- For eg. [3, 4] cannot contains [3, 3], so we need to put [3, 4] before [3, 3] when sorting otherwise it will be counted as an increasing number if the order is [3, 3], [3, 4]
Sorting the width reduces the problem by one dimension. If width is strictly increasing, the problem is equivalent to finding LIS in only the height dimension.
Now lets apply the LIS algo on height. We build a DP array.
In DP array, we fill in height from left to right. Initially all heights are 0.
- For first height, we check if binary search returns something. That is the left place where the height can be inserted. If that matches current index, we increment ans.

In java, instead of writing our own method, we can also use Arrays.binarySearch(int[] array, int fromIndex, int toIndex, int target) method.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(), envelopes.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] == b[0] ? b[1] > a[1] : a[0] < b[0];
        });
        vector<int> dp;
        for (auto& env : envelopes) {
            int h = env[1];
            auto it = lower_bound(dp.begin(), dp.end(), h);
            if (it == dp.end()) dp.push_back(h);
            else *it = h;
        }
        return dp.size();
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


import "sort"

type Solution struct{}

func (Solution) MaxEnvelopes(envelopes [][]int) int {
    sort.Slice(envelopes, func(i, j int) bool {
        if envelopes[i][0] == envelopes[j][0] {
            return envelopes[i][1] > envelopes[j][1]
        }
        return envelopes[i][0] < envelopes[j][0]
    })
    dp := []int{}
    for _, env := range envelopes {
        h := env[1]
        l, r := 0, len(dp)
        for l < r {
            m := l + (r-l)/2
            if dp[m] < h {
                l = m + 1
            } else {
                r = m
            }
        }
        if l == len(dp) {
            dp = append(dp, h)
        } else {
            dp[l] = h
        }
    }
    return len(dp)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
	public int maxEnvelopes(int[][] envelopes) {
		Arrays.sort(envelopes, (a,b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
		int[] dp = new int[envelopes.length];
		int ans = 0;
		for (int[] envelope : envelopes) {
			int height = envelope[1];
			int left = binarySearch(dp, 0, ans, height);
			if(left < 0) {
				left = -(left + 1);}
			if (left == ans) ans++;
			dp[left] = height;
		}
		return ans;
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution {
    fun maxEnvelopes(envelopes: Array<IntArray>): Int {
        envelopes.sortWith(compareBy({ it[0] }, { -it[1] }))
        val dp = mutableListOf<Int>()
        for (env in envelopes) {
            val h = env[1]
            val idx = dp.binarySearch(h)
            val insertIdx = if (idx < 0) -idx - 1 else idx
            if (insertIdx == dp.size) dp.add(h)
            else dp[insertIdx] = h
        }
        return dp.size
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


from bisect import bisect_left
from typing import List

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        envelopes.sort(key=lambda x: (x[0], -x[1]))
        dp = []
        for _, h in envelopes:
            idx = bisect_left(dp, h)
            if idx == len(dp):
                dp.append(h)
            else:
                dp[idx] = h
        return len(dp)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


impl Solution {
    pub fn max_envelopes(mut envelopes: Vec<Vec<i32>>) -> i32 {
        envelopes.sort_by(|a, b| {
            if a[0] == b[0] {
                b[1].cmp(&a[1])
            } else {
                a[0].cmp(&b[0])
            }
        });
        let mut dp = Vec::new();
        for env in envelopes {
            let h = env[1];
            match dp.binary_search(&h) {
                Ok(idx) | Err(idx) => {
                    if idx == dp.len() {
                        dp.push(h);
                    } else {
                        dp[idx] = h;
                    }
                }
            }
        }
        dp.len() as i32
    }
}

Dry Running the Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


sorted by width envelopes = [[1, 1], [2, 3], [4, 6], [4, 5], [6, 7]]

Searching for height of 1
Result of search: -1
Inserting height at index: 0
dp: 1 0 0 0 0 
l is now 1

Searching for height of 3
Result of search: -2
Inserting height at index: 1
dp: 1 3 0 0 0 
l is now 2

Searching for height of 6
Result of search: -3
Inserting height at index: 2
dp: 1 3 6 0 0 
l is now 3

Searching for height of 5
Result of search: -3
Inserting height at index: 2
dp: 1 3 5 0 0 
l is now 3

Searching for height of 7
Result of search: -4
Inserting height at index: 3
dp: 1 3 5 7 0 
l is now 4

Max number of envelopes: 4

Complexity

⏰ Time complexity: O(n log n). O(n log n) for sorting and O(n) for iterating.
🧺 Space complexity: O(n)

Problem#

Examples#

Constraints#

Solution#

Method 1 - Sort by Width and Use DP Like in LIS on Height#

Algo#

Code#

Complexity#

Method 2 - Sort by Width and Height and Do Binary Search on Height#

Algorithm#

Code#

Dry Running the Code#

Complexity#

Problem

Examples

Constraints

Solution

Method 1 - Sort by Width and Use DP Like in LIS on Height

Algo

Code

Complexity

Method 2 - Sort by Width and Height and Do Binary Search on Height

Algorithm

Code

Dry Running the Code

Complexity