// Runtime: 2 ms, faster than 99.97% of Java online submissions for Vertical Order Traversal of a Binary Tree.
// Memory Usage: 36.3 MB, less than 100.00% of Java online submissions for Vertical Order Traversal of a Binary Tree.
class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        Map<Integer, ArrayList<Pair>> map = new HashMap<>();
        traverse(root, 0, 0, map);

        List<List<Integer>> result = new LinkedList<>();

        ArrayList<Integer> xs = new ArrayList<>(map.keySet());
        Collections.sort(xs);

        for (int x: xs) {
            ArrayList<Pair> line = map.get(x);
            Collections.sort(line);

            List<Integer> r = new LinkedList<>();
            for (Pair p: line) r.add(p.val);

            result.add(r);
        }
        return result;
    }

    private void traverse(TreeNode root, int x, int y, Map<Integer, ArrayList<Pair>> map) {
        if (root == null) return;

        if (!map.containsKey(x)) map.put(x, new ArrayList<Pair>());
        map.get(x).add(new Pair(root.val, y));

        traverse(root.left, x-1, y-1, map);
        traverse(root.right, x+1, y-1, map);
    }

    class Pair implements Comparable<Pair> {
        public int val;
        public int y;

        public Pair(int val, int y) {
            this.val = val;
            this.y = y;
        }

        public int compareTo(Pair another) {
            int yDiff = -y + another.y;
            if (yDiff != 0) return yDiff;
            else return val - another.val;
        }
    }
}