Boxes All the Way Down - Amazon Top Interview Questions

                        Solution in C++ :

struct SegTree {
    int n;
    vector<int> arr;
    vector<int> tree;
    SegTree(int n1, vector<int>& a) {
        n = n1;
        arr = a;
        int s = 1;
        while (s < 2 * n) {
            s = s << 1;
        }
        tree.resize(s);
        fill(tree.begin(), tree.end(), 0);
        build(0, n - 1, 1);
    }
    void build(int start, int end, int index) {
        if (start == end) {
            arr[start] = tree[index];
            return;
        }
        int mid = (start + end) / 2;
        build(start, mid, index * 2);
        build(mid + 1, end, index * 2 + 1);
        tree[index] = max(tree[2 * index], tree[2 * index + 1]);
    }
    void update(int start, int end, int index, int idx, int value) {
        if (start == end) {
            arr[start] = max(arr[start], value);
            tree[index] = arr[start];
            return;
        }
        int mid = (start + end) / 2;
        if (idx <= mid)
            update(start, mid, index * 2, idx, value);
        else
            update(mid + 1, end, index * 2 + 1, idx, value);
        tree[index] = max(tree[2 * index], tree[2 * index + 1]);
    }
    int query(int start, int end, int index, int left, int right) {
        if (start > right || end < left) return 0;
        if (start >= left && end <= right) return tree[index];
        int mid = (start + end) / 2;
        int val1 = query(start, mid, index * 2, left, right);
        int val2 = query(mid + 1, end, index * 2 + 1, left, right);
        return max(val1, val2);
    }
};
bool compare(vector<int>& a, vector<int>& b) {
    return a[0] < b[0];
}
int solve(vector<vector<int>>& matrix) {
    map<int, int> compression;
    int n = matrix.size();
    for (int i = 0; i < n; i++) {
        compression[matrix[i][1]] = 0;
    }
    int last = 1;
    for (auto& i : compression) {
        i.second = last++;
    }
    for (int i = 0; i < n; i++) {
        matrix[i][1] = compression[matrix[i][1]];
    }
    sort(matrix.begin(), matrix.end(), compare);
    vector<vector<int>> points;
    int lastX = -1;
    vector<int> prev = {};
    for (int i = 0; i < n; i++) {
        if (matrix[i][0] != lastX) {
            if (prev.size() != 0) {
                points.push_back(prev);
                prev.clear();
            }
            prev.push_back(matrix[i][1]);
            lastX = matrix[i][0];
        } else {
            prev.push_back(matrix[i][1]);
        }
    }
    if (prev.size() != 0) {
        points.push_back(prev);
    }
    vector<int> ans(n + 1, 0);
    SegTree sg = SegTree(n + 1, ans);
    for (auto i : points) {
        vector<int> toUpdate;
        for (auto j : i) {
            int value = sg.query(0, n, 1, 0, j - 1);
            toUpdate.push_back(value + 1);
        }
        for (int j = 0; j < i.size(); j++) {
            sg.update(0, n, 1, i[j], toUpdate[j]);
        }
    }
    return sg.query(0, n, 1, 0, n);
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(int[][] A) {
        Arrays.sort(A, (a, b) -> {
            if (a[0] == b[0])
                return b[1] - a[1];
            return a[0] - b[0];
        });

        int B[] = new int[A.length];
        for (int i = 0; i < A.length; i++) {
            B[i] = A[i][1];
        }

        return lis(B);
    }

    public int lis(int[] A) {
        int dp[] = new int[A.length];
        Arrays.fill(dp, Integer.MAX_VALUE);
        for (int i = 0; i < A.length; i++) {
            bin(dp, A[i]);
        }
        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            if (dp[i] != Integer.MAX_VALUE)
                res = i + 1;
        }
        return res;
    }

    public void bin(int dp[], int val) {
        int l = 0, r = dp.length - 1;
        int index = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (val <= dp[mid]) {
                index = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        dp[index] = val;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, a):

        # double strict
        a.sort(key=lambda x: [x[0], -x[1]])

        ret = []

        for w, h in a:
            i = bisect_left(ret, h)
            ret[i : i + 1] = [h]

        return len(ret)