Chrono Messenger Optimization — Problem Statement & Solution Guide

HashingMediumMixed

TimeO(n log n)

SpaceO(n)

Problem Description

You are given an array of message objects, each containing a unique integer id and an integer timestamp indicating the time the message was created. The messenger system must deliver all messages respecting their temporal order: a message with a smaller timestamp must be delivered before any message with a larger timestamp. If two or more messages share the same timestamp, they should be delivered in ascending order of their id. Return an array consisting solely of the ids of the messages arranged in the order they will be delivered.

Input: An array messages where messages[i] is an object { "id": int, "timestamp": int }.

Output: An array of integers representing the ids of the messages sorted first by timestamp (non‑decreasing) and then by id (ascending) for ties.

DSA Pattern Breakdown

"Chrono Messenger Optimization"

medium

WHY DOES IT MATTER?

Ordering by timestamp is essential for consistency, causality, and user experience in messaging systems. Without a guaranteed order, users could see replies before the original message, leading to confusion and potential data integrity issues.

OPTIMIZATION CHALLENGE

The main challenge is reducing the time from O(n^2) pairwise comparisons to O(n log n) by using an efficient sorting algorithm while preserving stability for equal timestamps.

REAL-WORLD CONNECTION

In distributed databases, write operations are often ordered by logical clocks or timestamps to maintain serializability. Similarly, message brokers like Kafka use offsets and timestamps to ensure consumers read events in the correct sequence.

When implementing the solution, always use the language’s built‑in stable sort (e.g., Array.prototype.sort in JavaScript with a comparator) and test with edge cases where many messages share the same timestamp to confirm stability.

COMPLEXITY AT A GLANCE

⏱ Time:O(n log n)

💾 Space:O(n)

Core Theory — Why This Approach?

The problem reduces to ordering a collection of objects by a key—in this case, the integer timestamp. A naive approach would compare every pair of messages, leading to an O(n^2) time complexity that quickly becomes infeasible for large datasets. Modern programming languages provide highly optimized comparison‑based sorting routines that run in O(n log n) time and, when implemented with a stable sort, preserve the relative order of messages that share the same timestamp. This guarantees that the messenger system delivers messages in strict temporal order while respecting any required tie‑breaking rule (e.g., ascending id). If the range of timestamps is bounded and small, a counting or bucket sort can even bring the time down to O(n) at the cost of additional space, but for arbitrary timestamps the comparison‑based approach is both simple and optimal.

The key insight is that the ordering constraint is a total order on the timestamps, so the problem is essentially a sorting problem. By leveraging the fact that sorting algorithms are well‑studied, we avoid reinventing complex data structures such as priority queues or balanced trees, which would add unnecessary overhead. Instead, we simply sort the array once and then iterate through it to deliver the messages. This approach also makes the solution easy to reason about, test, and maintain—critical qualities for production code in distributed messaging systems.

In practice, the messenger system may receive messages in real time, but the core requirement remains: at any point, the next message to deliver must be the one with the smallest timestamp among those not yet delivered. By pre‑sorting the entire batch or maintaining a min‑heap for streaming input, we can guarantee that the delivery order is always correct while keeping the algorithmic complexity within acceptable bounds for both batch and online scenarios.

Interview Questions on This Problem

Q1How would you handle duplicate timestamps in the messenger system?

I would use a stable sort or include a secondary key such as the message id to break ties. This ensures that messages with the same timestamp are delivered in a deterministic order, which is important for consistency and debugging.

Q2What if the timestamps are extremely large but the number of messages is small?

The size of the timestamps does not affect the comparison‑based sort’s complexity; it only affects the cost of comparing two values. In such cases, I would still use an O(n log n) sort, possibly with a custom comparator that handles large integers efficiently, or use a radix sort if the timestamps fit within a fixed number of bits.

Q3How would you optimize the algorithm for a streaming input where messages arrive continuously?

I would maintain a min‑heap (priority queue) keyed by timestamp. Each new message is inserted in O(log n) time, and the next message to deliver is extracted in O(log n). This keeps the system responsive and ensures that the delivery order is always correct without needing to sort the entire dataset at once.

Examples

Example 1

Input

[{"id":12,"timestamp":5},{"id":7,"timestamp":3},{"id":9,"timestamp":5}]

Output

[7,12,9]

Explanation: The timestamps are 3, 5, 5. The message with `id` 7 has the smallest timestamp (3) and is delivered first. The remaining two messages share timestamp 5; they are ordered by `id`, so 12 comes before 9.

Example 2

Input

[{"id":101,"timestamp":1000},{"id":58,"timestamp":999},{"id":77,"timestamp":1000},{"id":42,"timestamp":998}]

Output

[42,58,101,77]

Explanation: Sorting by timestamp yields the order: 998 (id 42), 999 (id 58), then two messages with timestamp 1000. Between the latter, id 101 < id 77, so 101 is placed before 77.

Example 3

Input

[{"id":3,"timestamp":0},{"id":1,"timestamp":0},{"id":2,"timestamp":-1}]

Output

[2,1,3]

Explanation: The smallest timestamp is -1, belonging to `id` 2, so it is first. The remaining two messages both have timestamp 0; they are ordered by id, giving 1 before 3.

Constraints

1 <= messages.length <= 200000
All `id` values are distinct integers within the range [1, 10^9]
-10^12 <= timestamp <= 10^12
The algorithm should run in O(n log n) time or better and use O(n) additional memory

Optimal Approach & Strategy

Sort the array of messages by timestamp using a stable comparison sort, then iterate through the sorted array to deliver them. This runs in O(n log n) time and O(n) space.

Brute Force Approach

Compare each message with every other message to find the smallest timestamp, then deliver it and repeat. This takes O(n^2) time and is impractical for large inputs.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n log n)

/**
 * @param {number[][]} messages
 * @return {number[]}
 */
var chronoMessenger = function(messages) {
    const indices = messages.map((_, i) => i);
    indices.sort((a, b) => {
        if (messages[a][1] !== messages[b][1]) return messages[a][1] - messages[b][1];
        return messages[a][0] - messages[b][0];
    });
    return indices.map(i => messages[i][0]);
};

class Solution {
public:
    vector<int> chronoMessenger(vector<vector<int>>& messages) {
        vector<int> result;
        vector<int> indices(messages.size());
        for (int i = 0; i < messages.size(); ++i) indices[i] = i;
        sort(indices.begin(), indices.end(), [&](int a, int b) {
            if (messages[a][1] != messages[b][1]) return messages[a][1] < messages[b][1];
            return messages[a][0] < messages[b][0];
        });
        for (int idx : indices) result.push_back(messages[idx][0]);
        return result;
    }
};

class Solution {
    public List<Integer> chronoMessenger(int[][] messages) {
        Integer[] indices = new Integer[messages.length];
        for (int i = 0; i < messages.length; i++) indices[i] = i;
        Arrays.sort(indices, (a, b) -> {
            if (messages[a][1] != messages[b][1]) return messages[a][1] - messages[b][1];
            return messages[a][0] - messages[b][0];
        });
        List<Integer> result = new ArrayList<>();
        for (int idx : indices) result.add(messages[idx][0]);
        return result;
    }
}

class Solution:
    def chronoMessenger(self, messages: List[List[int]]) -> List[int]:
        indices = list(range(len(messages)))
        indices.sort(key=lambda i: (messages[i][1], messages[i][0]))
        return [messages[i][0] for i in indices]

/**
 * @param {number[][]} messages
 * @return {number[]}
 */
var chronoMessenger = function(messages) {
    const indices = messages.map((_, i) => i);
    indices.sort((a, b) => {
        if (messages[a][1] !== messages[b][1]) return messages[a][1] - messages[b][1];
        return messages[a][0] - messages[b][0];
    });
    return indices.map(i => messages[i][0]);
};

Asked in Top Tech Interviews

uncategorizedmediumgeneric

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.

Chrono Messenger Optimization Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Hashing

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Chrono Messenger Optimization — 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