Russian Doll Envelopes

Problem Statement

In this task, you are provided with a list of envelopes, each defined by its width (wi) and height (hi). These envelopes are given as a two-dimensional array envelopes, where each sub-array [wi, hi] represents the dimensions of one envelope.

The core challenge is determining how many envelopes can be nested inside each other, much like Russian nesting dolls. An envelope can fit into another only if both its width and height are strictly smaller than those of the other envelope. No rotations of the envelopes are allowed (i.e., you cannot swap width and height to make one fit into the other).

The objective is to find the maximum number of envelopes that can be nested in this manner.

Examples

Example 1

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

Input:

envelopes = [[1,1],[1,1],[1,1]]

Output:

1

Constraints

• 1 <= envelopes.length <= 105
• envelopes[i].length == 2
• 1 <= wi, hi <= 105

Approach and Intuition

The problem can be visualized as finding the longest increasing subsequence in two dimensions—one for width and another for height.

1. Sort the Envelopes: Start by sorting the array of envelopes. First by width in ascending order and if two envelopes have the same width, sort them by height in descending order. That way, when you iterate through the sorted list, you can focus only on increasing heights since the equal width condition will automatically be resolved (as no two envelopes of the same width should be considered in the sequence).

2. Dynamic Programming for Longest Increasing Subsequence (LIS): Once the envelopes are sorted, the task reduces to finding the longest increasing subsequence based on heights.

   • Initialize an array dp where dp[i] will eventually represent the length of the longest increasing subsequence ending at index i.
   • For each envelope, compare its height with all previous envelopes' heights. If the current envelope's height is greater and forms a longer sequence with a previous envelope, update dp[i].

3. Find the Maximum Value in dp:

   • Traverse through the dp array to find the maximum value, which represents the maximum number of envelopes you can Russian doll.

Example Walkthrough

• For example 1, after sorting by the provided strategy, the envelopes would look like: [[2, 3], [5, 4], [6, 4], [6, 7]].
• Then applying the LIS logic strictly on the heights would yield:
  • Start with [2, 3], here the sequence starts, dp = [1,..].
  • [5, 4] can contain [2, 3], so dp = [1, 2,..].
  • [6, 4] can't continue from [5, 4] due to the same height, so no change.
  • Finally, [6, 7] can contain [5, 4], updating dp = [1, 2, 2, 3].
• The maximum value in dp is 3, which represents the answer.

This method gives a clear path to determining the maximum number of envelopes one can nest inside another based on their width and height constraints.

Solutions

class Solution {
    
    public int findLISLength(int[] elements) {
        int[] seq = new int[elements.length];
        int sequenceLength = 0;
        for (int element : elements) {
            int pos = Arrays.binarySearch(seq, 0, sequenceLength, element);
            if (pos < 0) {
                pos = -(pos + 1);
            }
            seq[pos] = element;
            if (pos == sequenceLength) {
                sequenceLength++;
            }
        }
        return sequenceLength;
    }
    
    public int maximumEnvelopes(int[][] envelopes) {
        // First dimension ascending, second dimension descending if first is the same
        Arrays.sort(envelopes, new Comparator<int[]>() {
            public int compare(int[] envelope1, int[] envelope2) {
                if (envelope1[0] == envelope2[0]) {
                    return envelope2[1] - envelope1[1];
                } else {
                    return envelope1[0] - envelope2[0];
                }
            }
        });
        // Get the heights from the envelopes after sorting
        int[] heights = new int[envelopes.length];
        for (int i = 0; i < envelopes.length; ++i) heights[i] = envelopes[i][1];
        return findLISLength(heights);
    }
}