Problem Statement

A hash join is how databases efficiently join two tables on a shared key. It works in two phases:

1. Build phase: Scan one table and load its rows into a hash map keyed by the join column.
2. Probe phase: Scan the other table and look up each row's join key in the hash map to find matches.

Implement the HashJoin class that simulates this algorithm:

• HashJoin() initializes the join processor.
• void build(rows, int keyIndex) loads the build-side table. rows is a list of rows (each row is a list of values). keyIndex is the column index to use as the join key.
• List[List] probe(rows, int keyIndex) probes against the build-side table. For each probe row, find all build rows with a matching key. For each match, output a combined row: build_row + probe_row. Return all combined rows sorted lexicographically.

This is an inner join: only rows with matching keys on both sides appear in the output.

Additional information

• 0 <= len(rows) <= 10,000
• Each row contains 1 to 10 values (integers or strings).
• 0 <= keyIndex < len(row)
• A key may appear in multiple rows on either side (many-to-many join).
• build is called exactly once before probe.
• Output rows must be sorted lexicographically.

Example 1:

Input:
["HashJoin", "build", "probe"]
[[], [[[1,"Alice","Eng"],[2,"Bob","Sales"],[3,"Carol","Eng"]], 2],
    [[["Eng","BldgA"],["Sales","BldgB"],["Mkt","BldgC"]], 0]]

Output:
[null, null, [[1,"Alice","Eng","Eng","BldgA"],
              [2,"Bob","Sales","Sales","BldgB"],
              [3,"Carol","Eng","Eng","BldgA"]]]

Explanation: Alice and Carol are in "Eng" which matches the first probe row. Bob is in "Sales" which matches the second. "Mkt" has no match on the build side.

Example 2:

Input:
["HashJoin", "build", "probe"]
[[], [[[1,"a"],[1,"b"]], 0], [[[1,"x"],[1,"y"]], 0]]

Output:
[null, null, [[1,"a",1,"x"],[1,"a",1,"y"],[1,"b",1,"x"],[1,"b",1,"y"]]]

Explanation: Key 1 appears twice on each side, producing 2x2 = 4 combined rows (Cartesian product of matching rows).

Brute Force (Nested Loop Join)

Intuition

For each row in the probe table, scan every row in the build table looking for key matches. This is a direct simulation of a nested loop join.

Algorithm

1. Store the build rows.
2. On probe: for each probe row, iterate all build rows and check if build_row[buildKey] == probe_row[probeKey]. If so, concatenate and add to result.

class HashJoin:
    def __init__(self):
        self.build_rows = []
        self.build_key = 0

    def build(self, rows, keyIndex):
        self.build_rows = rows
        self.build_key = keyIndex

    def probe(self, rows, keyIndex):
        result = []
        for pr in rows:
            for br in self.build_rows:
                if br[self.build_key] == pr[keyIndex]:
                    result.append(br + pr)
        result.sort()
        return result

Time & Space Complexity

• Time complexity: O(n * m) per probe

• Reason: Every probe row is compared against every build row.

• Space complexity: O(n)

• Reason: Stores all build rows.

Hash Map Join (Optimal)

Intuition

Build a hash map from the build-side rows, keyed by the join column. Each key maps to a list of rows (to handle duplicates). During probe, look up each row's key in O(1) and emit all matches.

Algorithm

1. On build(rows, keyIndex): iterate rows, insert each into a defaultdict(list) keyed by row[keyIndex].
2. On probe(rows, keyIndex): for each probe row, look up row[keyIndex] in the hash map. For each matching build row, append build_row + probe_row to the result. Sort and return.

from collections import defaultdict

class HashJoin:
    def __init__(self):
        self.table = defaultdict(list)

    def build(self, rows, keyIndex):
        self.table.clear()
        for row in rows:
            self.table[row[keyIndex]].append(row)

    def probe(self, rows, keyIndex):
        result = []
        for row in rows:
            for build_row in self.table.get(row[keyIndex], []):
                result.append(build_row + row)
        result.sort()
        return result

Time & Space Complexity

• Time complexity: O(n + m + r log r) per probe

• Reason: Building the hash map is O(n). Probing is O(m) plus O(matches) for emitting rows. Sorting the output is O(r log r) where r is the result size.

• Space complexity: O(n + r)

• Reason: The hash map stores all n build rows. The result stores all r output rows.