Earliest Messages By Timestamp — Problem Statement & Solution Guide

StringsMediumMixed

TimeO(n)

SpaceO(k)

Problem Description

You are processing a log of network events where each entry consists of a unique alphanumeric message ID and a Unix timestamp (in seconds). Multiple messages may share the same timestamp, indicating they were received in the same processing batch. Your task is to identify, for every distinct timestamp present in the log, the message ID that corresponds to the earliest arrival within that specific batch. Since all messages within a batch share the same timestamp, 'earliest' is defined by the lexicographical order of the message IDs; the lexicographically smallest ID in a group is considered the primary or earliest message for that timestamp.

Given a list of message records, return a mapping where each key is a unique timestamp and the value is the lexicographically smallest message ID associated with that timestamp. The output should be a dictionary (or map) preserving the distinct timestamps as keys. If the input list is empty, return an empty map.

Note: Message IDs are case-sensitive strings. Lexicographical comparison follows standard ASCII ordering (e.g., 'A' < 'a', '1' < 'A').

DSA Pattern Breakdown

"Earliest Messages By Timestamp"

medium

WHY DOES IT MATTER?

This "first‑occurrence per key" pattern is essential for streaming data where order matters, enabling constant‑time updates and avoiding expensive re‑sorting. It is widely used in log aggregation, analytics, and real‑time dashboards.

OPTIMIZATION CHALLENGE

The critical insight is that the arrival order guarantees that the first time a key appears is the desired value, so we can skip any later occurrences without extra checks, reducing both time and space compared to sorting or nested scans.

REAL-WORLD CONNECTION

Consider a message broker that receives events from multiple producers. To display the first event per user session, you maintain a hash map of session IDs to the first event seen, updating it as events stream in. This mirrors the algorithmic pattern exactly.

When explaining this in an interview, emphasize the linear scan and the use of a hash map, and be ready to discuss edge cases like duplicate timestamps and how you preserve the original order.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(k)

Core Theory — Why This Approach?

The problem reduces to a classic "first occurrence per key" pattern. A naive approach might sort the log by timestamp and then scan for the first entry per timestamp, which would cost O(n log n) time and additional memory for sorting. However, because the log is already in arrival order, we can process it in a single pass, maintaining a hash map that records the first message ID seen for each timestamp. Whenever we encounter a timestamp not yet in the map, we insert the current message ID; subsequent entries with the same timestamp are ignored. This yields an optimal O(n) time solution with O(k) auxiliary space, where k is the number of distinct timestamps.

The key insight is that the arrival order of the log entries is the same as the order of processing, so the first time we see a timestamp is inherently the earliest arrival for that timestamp. By leveraging a hash map for constant‑time lookups and inserts, we avoid any need for sorting or nested loops, which would otherwise blow up the runtime on large inputs.

This pattern is a textbook example of "stream processing with stateful aggregation"—a technique that appears in many real‑world systems such as log analytics, event sourcing, and real‑time monitoring pipelines. It demonstrates how to turn a seemingly complex grouping problem into a simple linear scan when the data is already ordered appropriately.

Interview Questions on This Problem

Q1How would you modify the algorithm if the log entries were not guaranteed to be in arrival order?

If the log is unordered, you must first sort the entries by timestamp and then by original arrival index. After sorting, you can iterate and pick the first entry for each timestamp, which restores the earliest‑arrival semantics. This adds an O(n log n) sorting step but still keeps the subsequent scan linear.

Q2In a distributed system where logs are sharded across multiple machines, how can you efficiently compute the earliest message per timestamp?

Each shard can locally compute a map of timestamp to earliest message ID using the same single‑pass algorithm. Then a global aggregation step merges these maps by keeping the earliest message ID per timestamp across shards, which can be done with a reduce operation that compares timestamps and preserves the first occurrence.

Q3What trade‑offs arise if we need to support updates to the log after initial processing?

With updates, a simple hash map becomes insufficient because a new entry could become the earliest for its timestamp. One approach is to use a balanced BST or a priority queue keyed by (timestamp, arrivalIndex) to allow deletions and re‑insertion, but this increases complexity to O(log k) per update. Alternatively, you can batch updates and recompute the map periodically if real‑time accuracy is not critical.

Examples

Example 1

Input

messages = [["msg_101", 1620000000], ["msg_102", 1620000000], ["msg_100", 1620000000], ["msg_201", 1620000001]]

Output

{1620000000: "msg_100", 1620000001: "msg_201"}

Explanation: Group by timestamp: - Timestamp 1620000000 contains IDs: ["msg_101", "msg_102", "msg_100"]. Lexicographically, "msg_100" < "msg_101" < "msg_102". So, "msg_100" is the earliest. - Timestamp 1620000001 contains ID: ["msg_201"]. Only one ID, so "msg_201" is the earliest. Result: {1620000000: "msg_100", 1620000001: "msg_201"}

Example 2

Input

messages = [["A", 100], ["a", 100], ["B", 100], ["Z", 200]]

Output

{100: "A", 200: "Z"}

Explanation: Group by timestamp: - Timestamp 100 contains IDs: ["A", "a", "B"]. ASCII values: 'A'=65, 'a'=97, 'B'=66. Lexicographical order: "A" < "B" < "a". So, "A" is the earliest. - Timestamp 200 contains ID: ["Z"]. Only one ID, so "Z" is the earliest. Result: {100: "A", 200: "Z"}

Example 3

Input

messages = [["id_999", 500], ["id_1000", 500], ["id_99", 500]]

Output

{500: "id_1000"}

Explanation: Group by timestamp: - Timestamp 500 contains IDs: ["id_999", "id_1000", "id_99"]. Lexicographical comparison: - Compare "id_1000" vs "id_99": '1' (49) < '9' (57), so "id_1000" < "id_99". - Compare "id_1000" vs "id_999": '1' (49) < '9' (57), so "id_1000" < "id_999". - Thus, "id_1000" is the lexicographically smallest. Result: {500: "id_1000"}

Example 4

Input

messages = []

Output

{}

Explanation: The input list is empty. There are no timestamps to process. Return an empty map.

Constraints

0 <= messages.length <= 10^5
messages[i].length == 2
1 <= messages[i][0].length <= 100
messages[i][0] consists of uppercase/lowercase English letters and digits
0 <= messages[i][1] <= 10^9

Optimal Approach & Strategy

Process the log in a single pass, using a hash map to record the first message ID for each timestamp. Insert only when a timestamp is seen for the first time, achieving O(n) time and O(k) space.

Brute Force Approach

A naive solution would sort the log by timestamp and then scan to pick the first entry for each timestamp, costing O(n log n) time. Alternatively, you could use nested loops to compare each pair of entries, leading to O(n^2) time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function solution(messages) {
   // Sort the input array based on the timestamp
   messages.sort((a, b) => new Date(a[1]) - new Date(b[1]));
   
   // Initialize an empty list to store the result
   let result = [];
   
   // Iterate through the sorted array and add each message to the result list if it's the earliest message received from its timestamp
   let currentTimestamp = messages[0][1];
   let currentMessageId = messages[0][0];
   result.push([currentMessageId, currentTimestamp]);
   
   for (let i = 1; i < messages.length; i++) {
       if (messages[i][1] !== currentTimestamp) {
           currentTimestamp = messages[i][1];
           currentMessageId = messages[i][0];
           result.push([currentMessageId, currentTimestamp]);
       } else if (messages[i][0] !== currentMessageId) {
           currentMessageId = messages[i][0];
           result.push([currentMessageId, currentTimestamp]);
       }
   }
   
   return result;
}

class Solution {
public:
   vector<vector<int>> solution(vector<vector<int>>& messages) {
       // Sort the input array based on the timestamp
       sort(messages.begin(), messages.end(), [](const vector<int>& a, const vector<int>& b) {
           return a[1] < b[1];
       });
       
       // Initialize an empty list to store the result
       vector<vector<int>> result;
       
       // Iterate through the sorted array and add each message to the result list if it's the earliest message received from its timestamp
       int currentTimestamp = messages[0][1];
       int currentMessageId = messages[0][0];
       result.push_back({currentMessageId, currentTimestamp});
       
       for (int i = 1; i < messages.size(); i++) {
           if (messages[i][1] != currentTimestamp) {
               currentTimestamp = messages[i][1];
               currentMessageId = messages[i][0];
               result.push_back({currentMessageId, currentTimestamp});
           } else if (messages[i][0] != currentMessageId) {
               currentMessageId = messages[i][0];
               result.push_back({currentMessageId, currentTimestamp});
           }
       }
       
       return result;
   }
}

class Solution {
   public int solution(int[][] messages) {
       // Sort the input array based on the timestamp
       Arrays.sort(messages, (a, b) -> a[1].compareTo(b[1]));
       
       // Initialize an empty list to store the result
       List<int[]> result = new ArrayList<>();
       
       // Iterate through the sorted array and add each message to the result list if it's the earliest message received from its timestamp
       int currentTimestamp = messages[0][1];
       int currentMessageId = messages[0][0];
       result.add(new int[] {currentMessageId, currentTimestamp});
       
       for (int i = 1; i < messages.length; i++) {
           if (messages[i][1] != currentTimestamp) {
               currentTimestamp = messages[i][1];
               currentMessageId = messages[i][0];
               result.add(new int[] {currentMessageId, currentTimestamp});
           } else if (messages[i][0] != currentMessageId) {
               currentMessageId = messages[i][0];
               result.add(new int[] {currentMessageId, currentTimestamp});
           }
       }
       
       return result.toArray(new int[0][]);
   }
}

def solution(messages):
   # Sort the input array based on the timestamp
   messages.sort(key=lambda x: x[1])
   
   # Initialize an empty list to store the result
   result = []
   
   # Iterate through the sorted array and add each message to the result list if it's the earliest message received from its timestamp
   current_timestamp = messages[0][1]
   current_message_id = messages[0][0]
   result.append([current_message_id, current_timestamp])
   
   for i in range(1, len(messages)):
       if messages[i][1] != current_timestamp:
           current_timestamp = messages[i][1]
           current_message_id = messages[i][0]
           result.append([current_message_id, current_timestamp])
       elif messages[i][0] != current_message_id:
           current_message_id = messages[i][0]
           result.append([current_message_id, current_timestamp])
   
   return result

function solution(messages) {
   // Sort the input array based on the timestamp
   messages.sort((a, b) => new Date(a[1]) - new Date(b[1]));
   
   // Initialize an empty list to store the result
   let result = [];
   
   // Iterate through the sorted array and add each message to the result list if it's the earliest message received from its timestamp
   let currentTimestamp = messages[0][1];
   let currentMessageId = messages[0][0];
   result.push([currentMessageId, currentTimestamp]);
   
   for (let i = 1; i < messages.length; i++) {
       if (messages[i][1] !== currentTimestamp) {
           currentTimestamp = messages[i][1];
           currentMessageId = messages[i][0];
           result.push([currentMessageId, currentTimestamp]);
       } else if (messages[i][0] !== currentMessageId) {
           currentMessageId = messages[i][0];
           result.push([currentMessageId, currentTimestamp]);
       }
   }
   
   return result;
}

Asked in Top Tech Interviews

stringsmediumnone

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.

Earliest Messages By Timestamp Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Strings

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Earliest Messages By Timestamp — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor