Sorted Message Timeline — Problem Statement & Solution Guide
Problem Description
You are provided with a 2D integer array events, where each sub-array events[i] consists of two integers: [identifier, epoch]. The identifier is a unique integer representing a specific system event, and epoch is a Unix timestamp indicating when the event occurred.
Your task is to reconstruct the chronological sequence of these events. Sort the array in ascending order based on the epoch value. In the case of a tie, where two or more events share the same epoch, resolve the ambiguity by sorting those specific events in ascending order of their identifier.
Return the sorted 2D array representing the reconstructed timeline.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Sorted Message Timeline"
WHY DOES IT MATTER?
Sorting by a key is a foundational pattern that appears in log aggregation, timeline reconstruction, and any scenario where chronological ordering is required. Mastery of efficient sorting directly impacts system latency and throughput.
OPTIMIZATION CHALLENGE
The key insight is recognizing that the problem is a pure sort on a single attribute, allowing us to bypass any O(N^2) pairwise comparison and instead apply a proven O(N log N) algorithm or a linear‑time bucket/counting sort when the key domain is bounded.
REAL-WORLD CONNECTION
Think of a distributed logging service that receives events from many micro‑services. To present a coherent timeline to an operator, the service must merge and sort the incoming timestamped logs, similar to how Kafka partitions are merged into a single ordered stream.
In an interview, start by stating the naive O(N^2) idea, then immediately pivot to the optimal O(N log N) sort, mentioning language‑specific stable sorts (TimSort) and discussing space trade‑offs (in‑place heap vs. extra buffer).
COMPLEXITY AT A GLANCE
O(N log N)O(1) auxiliary (in‑place heap) or O(N) if using mergesort/TimsortCore Theory — Why This Approach?
The problem reduces to sorting a list of pairs by the second element (epoch). A stable sort is not required because identifiers are unique, but using a comparison‑based sort guarantees O(N log N) time, which is optimal for arbitrary inputs under the comparison model. Naïve approaches such as bubble sort or insertion sort degrade to O(N^2) on large N, quickly exceeding time limits for typical interview constraints (e.g., N up to 10^5 or 10^6). By leveraging the divide‑and‑conquer paradigm of mergesort or the heap‑based approach of heapsort, we can achieve the lower bound of O(N log N) while keeping auxiliary space modest. In languages with built‑in efficient sort (TimSort in Python/Java, introsort in C++), the implementation automatically adapts to partially ordered data, further improving real‑world performance.
Interview Questions on This Problem
Q1How would you sort a list of events by timestamp if the timestamps are guaranteed to be within a small fixed range (e.g., 0‑10^6)?
Use counting sort or bucket sort, which runs in O(N + K) time where K is the range size. Since K is small relative to N, this becomes linear, and it also uses O(K) extra space.
Q2Can you sort the events in‑place without using extra memory beyond O(1)? Which algorithm would you choose and why?
Heapsort sorts in‑place with O(1) auxiliary space and O(N log N) time. It builds a max‑heap in‑place and repeatedly extracts the maximum, placing it at the end of the array.
Q3If the input array is already partially sorted (e.g., each event is at most 5 positions away from its final position), which sorting algorithm gives the best practical performance?
Insertion sort runs in O(N · k) where k is the maximum displacement; with k = 5 it becomes linear. Alternatively, using a min‑heap of size k+1 (a “k‑sorted” or “almost sorted” approach) yields O(N log k) time.
Examples
Input
events = [[10, 100], [5, 200], [10, 100], [1, 100]]
Output
[[1, 100], [10, 100], [10, 100], [5, 200]]
Explanation: First, identify events with the minimum epoch (100). These are [10, 100], [10, 100], and [1, 100]. Sort these by identifier: 1 comes before 10. Thus, [1, 100] is first, followed by the two [10, 100] entries. The remaining event [5, 200] has a higher epoch, so it is placed last.
Input
events = [[1, 5], [2, 5], [3, 5]]
Output
[[1, 5], [2, 5], [3, 5]]
Explanation: All events share the same epoch (5). Therefore, the sorting is determined entirely by the identifier in ascending order: 1, then 2, then 3.
Input
events = [[99, 1000], [1, 2000], [50, 1500]]
Output
[[99, 1000], [50, 1500], [1, 2000]]
Explanation: The epochs are 1000, 2000, and 1500. Sorting by epoch ascending gives the order 1000, 1500, 2000. The corresponding identifiers are 99, 50, and 1. Since all epochs are unique, no tie-breaking by identifier is needed.
Constraints
- 1 <= events.length <= 10^5
- events[i].length == 2
- 1 <= events[i][0] <= 10^9
- 1 <= events[i][1] <= 10^9
- All identifiers in events are unique.
Optimal Approach & Strategy
Apply a comparison‑based sort (e.g., quicksort, mergesort, or the language's built‑in sort) on the array using the epoch as the key, achieving O(N log N) time.
Brute Force Approach
Iterate over every pair of events and swap them if they are out of order (bubble sort), resulting in O(N^2) time.
Verified Code Solutions
function solution(messages) { return messages.sort((a, b) => a[1] - b[1] || a[0] - b[0]); }class Solution { public: vector<vector<int>> solution(vector<vector<int>>& messages) { sort(messages.begin(), messages.end(), [](const vector<int>& a, const vector<int>& b) { return a[1] == b[1] ? a[0] < b[0] : a[1] < b[1]; }); return messages; } };import java.util.Arrays; class Solution { public int[][] solution(int[][] messages) { Arrays.sort(messages, (a, b) -> a[1] == b[1] ? a[0] - b[0] : a[1] - b[1]); return messages; } }def solution(messages): return sorted(messages, key=lambda x: (x[1], x[0]))function solution(messages) { return messages.sort((a, b) => a[1] - b[1] || a[0] - b[0]); }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.