Skip to content

354. Russian Doll Envelopes 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(n)$
 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
class Solution {
 public:
  int maxEnvelopes(vector<vector<int>>& envelopes) {
    ranges::sort(envelopes, ranges::less{}, [](const vector<int>& envelope) {
      const int w = envelope[0];
      const int h = envelope[1];
      return pair<int, int>{w, -h};
    });
    return lengthOfLIS(envelopes);
  }

 private:
  // Same to 300. Longest Increasing Subsequence
  int lengthOfLIS(vector<vector<int>>& envelopes) {
    // tails[i] := the minimum tail of all the increasing subsequences having
    // length i + 1
    vector<int> tails;

    for (const vector<int>& envelope : envelopes) {
      const int h = envelope[1];
      if (tails.empty() || h > tails.back())
        tails.push_back(h);
      else
        tails[firstGreaterEqual(tails, h)] = h;
    }

    return tails.size();
  }

 private:
  int firstGreaterEqual(const vector<int>& arr, int target) {
    return ranges::lower_bound(arr, target) - arr.begin();
  }
};

 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
class Solution {
  public int maxEnvelopes(int[][] envelopes) {
    Arrays.sort(envelopes, Comparator.comparingInt((int[] envelope) -> envelope[0])
                               .thenComparingInt((int[] envelope) -> - envelope[1]));
    return lengthOfLIS(envelopes);
  }

  // Similar to 300. Longest Increasing Subsequence
  private int lengthOfLIS(int[][] envelopes) {
    // tails[i] := the minimum tail of all the increasing subsequences having
    // length i + 1
    List<Integer> tails = new ArrayList<>();

    for (final int[] envelope : envelopes) {
      final int h = envelope[1];
      if (tails.isEmpty() || h > tails.get(tails.size() - 1))
        tails.add(h);
      else
        tails.set(firstGreaterEqual(tails, h), h);
    }

    return tails.size();
  }

  private int firstGreaterEqual(List<Integer> arr, int target) {
    final int i = Collections.binarySearch(arr, target);
    return i < 0 ? -i - 1 : i;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def maxEnvelopes(self, envelopes: list[list[int]]) -> int:
    envelopes.sort(key=lambda x: (x[0], -x[1]))
    return self._lengthOfLIS(envelopes)

  def _lengthOfLIS(self, envelopes: list[list[int]]) -> int:
    # tails[i] := the minimum tails of all the increasing subsequences having
    # length i + 1
    tails = []

    for _, h in envelopes:
      if not tails or h > tails[-1]:
        tails.append(h)
      else:
        tails[bisect.bisect_left(tails, h)] = h

    return len(tails)