Merging Two Sorted Lists by City and Timestamp
You have two sorted lists of records, each sorted first by city name and then by timestamp within each city. Merge them into a single sorted list (same sort order) in $O(n + m)$ time, where $n$ and $m$ are the sizes of the two lists.
Constraints: - Both lists are pre-sorted by (city, timestamp) - $1 \leq n, m \leq 10^6$ - City names are arbitrary strings; timestamps are comparable integers - The merge should be stable (equal timestamps preserve original relative order)
Example:
List 1: [(Austin, 1), (Austin, 3), (Boston, 2)] List 2: [(Austin, 2), (Boston, 1), (Boston, 4)] Output: [(Austin, 1), (Austin, 2), (Austin, 3), (Boston, 1), (Boston, 2), (Boston, 4)]
Hints
- Both input lists are sorted by (city, timestamp). Use that structure: first split each list by city, then merge per-city timestamp sequences.
- Group entries by city using a hash map (one pass each list). Within each city bucket, entries are already sorted by timestamp -- so a two-pointer merge takes $O(|A_c| + |B_c|)$ per city.
- Sum over all cities: $\sum_c (|A_c| + |B_c|) = n + m$. So the total work across all per-city merges is $O(n+m)$, same as a single global merge.
Worked Solution
How to Think About It: The two input lists are each already sorted by the *compound* key (city, timestamp), and the output must be sorted by the same key. Whenever you must merge two sequences that are each already sorted by the very key you want in the output, the textbook tool is a single two-pointer merge -- the same merge step as in mergesort. The only twist here is that the comparison key is a pair, but pairs have a perfectly good total order (lexicographic: compare city first, break ties by timestamp). There is no need to bucket by city or to sort the set of distinct cities; doing so would needlessly add an $O(C\log C)$ term. A flat two-pointer pass over the lexicographic key is already globally correct and runs in $O(n+m)$.
Why the naive "bucket and sort cities" idea is unnecessary (and slower). One might think you must first group records by city and then arrange the city groups in order, which costs $O(C\log C)$ to sort the $C$ distinct city names. But that work is redundant: because each input list is *already* in (city, timestamp) order, the smaller of the two current heads under the lexicographic key is always the global next record. The two-pointer merge discovers the correct city ordering for free as it advances -- it never needs an explicit sort of the city keys.
Approach: Keep one pointer into each list. Repeatedly append whichever current record has the smaller (city, timestamp) key; on an exact key tie, take from list 1 first to preserve stability. When one list is exhausted, append the remainder of the other.
```python def merge_city_time(list1, list2): i = j = 0 n, m = len(list1), len(list2) result = [] while i < n and j < m: a, b = list1[i], list2[j] # Lexicographic key: city first, then timestamp. # Use <= so ties (equal city AND equal timestamp) take list1 first -> stable. if (a[0], a[1]) <= (b[0], b[1]): # records are [city, timestamp] lists result.append(a); i += 1 else: result.append(b); j += 1 # One list is now exhausted; append whatever remains of the other. result.extend(list1[i:]) result.extend(list2[j:]) return result ```
Worked example. - List 1: [(Austin,1), (Austin,3), (Boston,2)], List 2: [(Austin,2), (Boston,1), (Boston,4)]. - Compare (Austin,1) vs (Austin,2) -> take (Austin,1). Then (Austin,3) vs (Austin,2) -> take (Austin,2). Then (Austin,3) vs (Boston,1) -> take (Austin,3). Then (Boston,2) vs (Boston,1) -> take (Boston,1). Then (Boston,2) vs (Boston,4) -> take (Boston,2). List 1 exhausted; append (Boston,4). - Output: [(Austin,1), (Austin,2), (Austin,3), (Boston,1), (Boston,2), (Boston,4)] -- exactly as required.
Complexity. - Time: $O(n+m)$. Each iteration appends exactly one record and advances one pointer, so there are at most $n+m$ iterations; each does an $O(1)$ tuple comparison (string-equality on cities aside, comparisons are constant in the usual model). No sorting of city keys is performed, so there is no $O(C\log C)$ term. - Space: $O(1)$ auxiliary beyond the output list itself (just two indices); the output is necessarily $O(n+m)$.
Stability. Using <= (rather than <) when the full keys tie means equal-key records from list 1 are emitted before those from list 2, and within a single list the original relative order is preserved because we advance that list's pointer in order. So the merge is stable.
Answer: Run a single two-pointer merge over the lexicographic key (city, then timestamp): at each step append the record with the smaller key, breaking exact-key ties by taking from list 1 first, then append the remainder of whichever list is left. This is $O(n+m)$ time, $O(1)$ extra space (besides the output), and stable -- no bucketing or city-key sort is needed.
Intuition
This problem demonstrates a general technique: if data has a hierarchical key structure, solve it hierarchically. Merging by (city, timestamp) is easier than merging by a single flat key because the problem decomposes: each city is an independent merge instance. The hash-map bucketing step pays $O(n+m)$ to do this decomposition, and then each sub-problem is solved independently with a linear scan.
The pattern is ubiquitous in finance data engineering. Trading data is typically keyed by (symbol, timestamp) or (exchange, timestamp). When merging feeds from two data providers -- both sorted by (symbol, timestamp) -- the hash-bucket-then-two-pointer approach is exactly what you want. It is also embarrassingly parallelizable: once bucketed by city/symbol, each city's merge can run on a separate CPU core with no coordination needed. That is a much harder property to exploit if you treat it as a flat sort-merge problem.