<commit_before>import collections
import unittest
from typing import Optional, List

import utils
from tree import TreeNode


# O(n) time. O(n) space. BFS, hash table.
class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        matrix = []
        queue = [(root, 0)]
        min_col = 0
        max_col = 0

        while queue:
            new_queue = []
            row = collections.defaultdict(list)
            matrix.append(row)

            for curr, c in queue:
                row[c].append(curr.val)

                if min_col > c:
                    min_col = c
                if max_col < c:
                    max_col = c

                if curr.left:
                    new_queue.append((curr.left, c - 1))
                if curr.right:
                    new_queue.append((curr.right, c + 1))

            queue = new_queue

        result = []

        for c in range(min_col, max_col + 1):
            col = []
            result.append(col)
            for row in matrix:
                row[c].sort()
                col += row[c]

        return result


class Test(unittest.TestCase):
    def test(self):
        utils.test(self, __file__, Solution, process_args=TreeNode.from_root_array)


if __name__ == '__main__':
    unittest.main()<commit_msg>987. Vertical Order Traversal of a Binary Tree<commit_after>import unittest
from typing import Optional, List

import utils
from tree import TreeNode


# O(n) time. O(n) space. BFS, hash table.
class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        cols = {}
        queue = [(root, 0)]
        min_col = 0
        max_col = 0

        while queue:
            new_queue = []
            row = {}

            for curr, c in queue:
                cell = row.get(c, None)
                if cell is None:
                    row[c] = [curr.val]
                else:
                    cell.append(curr.val)

                if min_col > c:
                    min_col = c
                if max_col < c:
                    max_col = c

                if curr.left:
                    new_queue.append((curr.left, c - 1))
                if curr.right:
                    new_queue.append((curr.right, c + 1))

            for c, cell in row.items():
                cell.sort()
                col = cols.get(c, None)
                if col is None:
                    cols[c] = cell
                else:
                    col += cell

            queue = new_queue

        result = []
        for c in range(min_col, max_col + 1):
            result.append(cols[c])

        return result


class Test(unittest.TestCase):
    def test(self):
        utils.test(self, __file__, Solution, process_args=TreeNode.from_root_array)


if __name__ == '__main__':
    unittest.main()
{'fraction_non_alphanumeric': 0.09687287559483344, 'fraction_numerical': 0.005098572399728076, 'mean_word_length': 1.3246445497630333, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2195690', 'n_tokens_mistral': 889, 'n_tokens_neox': 819, 'n_words': 232}