1
class Solution {
2
  public int maxEnvelopes(int[][] envelopes) {
3
    // sort the envelopes considering only width
4
    Arrays.sort(envelopes, new sortEnvelopes());
5

6
    // Now this is a Longest Increasing Subsequence problem on heights
7
    // tempList to store the temporary elements, size of this list will be the length of LIS
8
    ArrayList<Integer> tempList = new ArrayList<>();
9
    tempList.add(envelopes[0][1]);
10

11
    for (int i = 1; i < envelopes.length; i++) {
12
      if (envelopes[i][1] > tempList.get(tempList.size() - 1)) {
13
        tempList.add(envelopes[i][1]);
14
      } else {
15
        // if the element is smaller than the largest(last because it is sorted) element of
16
        // tempList, replace the largest smaller element of tempList with it..
17
        // ex->(assume if envelopes[i][1] is 4), then >>[1,7,8] will become [1,4,8]<<
18
        int index = lowerBound(tempList, envelopes[i][1]);
19
        tempList.set(index, envelopes[i][1]);
20
      }
21
    }
22
    return tempList.size();
23
  }
24

25
  // finding the index of greatest smaller element
26
  public int lowerBound(ArrayList<Integer> list, int search) {
27
    int start = 0;
28
    int end = list.size() - 1;
29
    while (start < end) {
30
      int mid = start + (end - start) / 2;
31
      if (list.get(mid) < search) {
32
        start = mid + 1;
33
      } else {
34
        end = mid;
35
      }
36
    }
37
    return start;
38
  }
39
}
40

41
class sortEnvelopes implements Comparator<int[]> {
42
  public int compare(int[] a, int[] b) {
43
    if (a[0] == b[0]) {
44
      // to ignore the duplicates, we are sorting such that, for same width-> element with
45
      // largest height would be considered first, in this way all the other smaller heights would
46
      // be ignored
47
      return b[1] - a[1];
48
    } else {
49
      return a[0] - b[0];
50
    }
51
  }
52
}