Simple Java Graph based solution (bad performance)
Came up with this different approach to the problem. I figured we could model these envelopes as a graph where an edge from n1 -> n2 would mean that n1 can enve
Came up with this different approach to the problem. I figured we could model these envelopes as a graph where an edge from n1 -> n2 would mean that n1 can envelope n2 [n1.width > n2.width && n1.height > n2.height]. Now that we have the graph, we can find the longest path and the length of that would give us the answer. I cached the longest path from nodes to avoid recurring subproblems, to avoid TLE. \n\nRuntime : 1131ms. faster than 5% of the submissions\nMemory: 111.4mb, less than 7.69% of the submissions\n\nDefinitely not the best approach but a possible one. \n\n```\nclass Node {\n    int width;\n    int height;\n    public List<Node> canHold = new ArrayList<>();\n    \n    @Override\n    public String toString() {\n        return "Node[" + this.width + "][" + this.height + "]";\n    }\n    Node(int width, int height) {\n        this.width = width;\n        this.height = height;\n    }\n    \n    public void checkHold(Node n) {\n        if(this.width > n.width && this.height > n.height) {\n            canHold.add(n);\n        }\n    }\n}\nclass Solution {\n    public List<Node> path;\n    public Map<Node, Integer> cache = new HashMap<>();\n    public int getMaxDistanceHelper(Node n, int distance) {\n        \n        if(cache.get(n) == null) {\n            int result;\n            if(n.canHold.size() == 0) \n                result = distance;\n            else {\n                int max = 0;\n                for(Node n2 : n.canHold) {\n                    int temp = 1 + getMaxDistanceHelper(n2, distance);\n                    if(temp > max)\n                        max = temp;\n                }\n                result = max;            \n            }   \n            cache.put(n, result);\n        }\n        return cache.get(n);\n    }\n    public int maxEnvelopes(int[][] envelopes) {\n        List<Node> nodes = new ArrayList<>();\n        \n        for(int i = 0; i < envelopes.length; i++) {\n            nodes.add(new Node(envelopes[i][0], envelopes[i][1]));\n        }\n        for(int i = 0; i < nodes.size(); i++) {\n            for(int j = 0; j < nodes.size(); j++) {\n                if(i != j) \n                    nodes.get(i).checkHold(nodes.get(j));\n            }\n        }\n\n        int max = 0;\n        for(Node n: nodes) {\n            \n            int dist = getMaxDistanceHelper(n, 1);\n            if(dist > max)\n                max = dist;\n        }\n        return max;\n    }\n}\n```
['Graph']