Timestamp Priority Sort — Problem Statement & Solution Guide

SortingMediumMixed

TimeO(n log n)

SpaceO(log n)

Problem Description

You are given an array of log entries, where each entry is represented as a pair of integers [t, p]. The first integer t denotes the timestamp, and the second integer p denotes the priority level. Your task is to reorder the entries according to a specific composite sorting rule.

The primary sorting criterion is the timestamp t in ascending order. If two or more entries share the same timestamp, they must be sorted by their priority level p in descending order. This ensures that within the same time window, higher-priority events appear before lower-priority ones.

Return the reordered array of pairs. The input array is not guaranteed to be sorted, and you may assume that all timestamps and priority levels are integers within a defined range. The solution must handle ties correctly and produce a stable, deterministic output based solely on the defined ordering rules.

DSA Pattern Breakdown

"Timestamp Priority Sort"

medium

WHY DOES IT MATTER?

Composite key sorting is fundamental in data engineering, database indexing, and real-time analytics. Understanding how to define and implement custom comparators correctly is essential for handling multi-dimensional data where order matters for business logic, such as prioritizing urgent events in a stream.

OPTIMIZATION CHALLENGE

The key insight is to avoid multiple passes over the data. A naive approach might sort by priority first, then by timestamp, but this fails if the sort is not stable or if the secondary sort overwrites the primary order. The optimal approach is a single pass with a composite comparator that encapsulates the entire sorting logic, ensuring O(n log n) time complexity without extra space for intermediate arrays.

REAL-WORLD CONNECTION

This pattern is directly analogous to how database systems handle multi-column indexes. For example, an index on (timestamp, priority) allows a database to quickly retrieve logs sorted by time, with priority as a tie-breaker. It is also similar to how email clients sort messages by date, with unread or high-priority emails appearing first within the same date.

In interviews, always clarify the tie-breaking rule explicitly. Ask if the priority sort is ascending or descending. Then, write the comparator carefully, ensuring that you return 0 only when both timestamp and priority are equal. Mentioning the stability of the underlying sort algorithm (like Timsort) shows depth of understanding.

COMPLEXITY AT A GLANCE

⏱ Time:O(n log n)

💾 Space:O(log n)

Core Theory — Why This Approach?

The problem of sorting log entries by a composite key (timestamp ascending, then priority descending) is a classic application of stable sorting algorithms. While the primary criterion is straightforward, the secondary criterion introduces a dependency that naive approaches often mishandle. In large-scale systems, log volumes can reach millions of entries per second, making O(n^2) algorithms like Bubble Sort or Selection Sort computationally infeasible. The optimal paradigm relies on O(n log n) comparison-based sorting, specifically leveraging the stability of algorithms like Merge Sort or the optimized Timsort used in Python and Java. Stability is crucial here because it ensures that if two entries have the same timestamp, their relative order from the initial array is preserved unless explicitly overridden by the secondary key. However, since we have a specific secondary key (priority), we must define a custom comparator that first compares timestamps and only falls back to priority if timestamps are equal.

Interview Questions on This Problem

Q1At a fintech platform, you need to sort transaction logs by time, but for simultaneous transactions, higher priority (e.g., fraud alerts) must appear before lower priority ones. How would you implement this efficiently in Java?

I would use Collections.sort() with a custom Comparator. The comparator first compares the timestamp fields using Integer.compare(t1, t2). If the result is 0, it then compares the priority fields in reverse order using Integer.compare(p2, p1) to ensure higher priority comes first. This leverages Timsort's O(n log n) performance and handles the composite key logic cleanly without manual array manipulation.

Q2In a high-growth startup, you are building a real-time dashboard that displays the last 10,000 log entries. The backend sends unsorted chunks. How do you maintain a sorted view with minimal latency?

I would use a min-heap or a balanced binary search tree (like a TreeMap in Java) keyed by timestamp, with a secondary key for priority. For each new chunk, I insert entries into the structure. Since we only need the last 10,000, I can maintain a bounded priority queue. However, for full sorting of the batch, I would merge the new chunk with the existing sorted list using a merge step, which is O(n) if both are sorted, or simply re-sort the combined list if the chunk size is small relative to the total, leveraging the fact that Timsort is efficient on partially sorted data.

Q3At a global product company, you notice that sorting 1 million log entries takes longer than expected. You suspect the comparator is the bottleneck. How do you optimize the sorting process?

I would first ensure the comparator is lightweight, avoiding object creation or complex calculations inside the compare method. I would also consider using a radix sort if the timestamps are integers within a known range, as radix sort is O(nk) and can outperform comparison sorts for integer keys. Additionally, I would check if the data is already partially sorted, as Timsort exploits existing runs to reduce comparisons. Profiling the comparator calls would confirm if the overhead is in the comparison logic or the sorting algorithm itself.

Examples

Example 1

Input

[[10, 5], [10, 8], [12, 3], [10, 2], [12, 7]]

Output

[[10, 8], [10, 5], [10, 2], [12, 7], [12, 3]]

Explanation: First, group by timestamp: entries with t=10 are [10,5], [10,8], [10,2]; entries with t=12 are [12,3], [12,7]. Sort each group by priority descending: for t=10, order is 8 > 5 > 2, yielding [10,8], [10,5], [10,2]. For t=12, order is 7 > 3, yielding [12,7], [12,3]. Concatenate groups in ascending timestamp order: [10,8], [10,5], [10,2], [12,7], [12,3].

Example 2

Input

[[5, 1], [5, 1], [5, 1]]

Output

[[5, 1], [5, 1], [5, 1]]

Explanation: All entries have identical timestamps (t=5) and identical priorities (p=1). Since both sorting keys are equal, the relative order remains unchanged. The output is identical to the input.

Example 3

Input

[[1, 100], [2, 1], [1, 99], [2, 2], [3, 50]]

Output

[[1, 100], [1, 99], [2, 2], [2, 1], [3, 50]]

Explanation: Group by timestamp: t=1 has [1,100], [1,99]; t=2 has [2,1], [2,2]; t=3 has [3,50]. Sort each group by priority descending: t=1 -> [1,100], [1,99]; t=2 -> [2,2], [2,1]; t=3 -> [3,50]. Concatenate in ascending timestamp order: [1,100], [1,99], [2,2], [2,1], [3,50].

Example 4

Input

[[7, 3], [7, 3], [8, 1], [7, 4], [8, 2]]

Output

[[7, 4], [7, 3], [7, 3], [8, 2], [8, 1]]

Explanation: Group by timestamp: t=7 has [7,3], [7,3], [7,4]; t=8 has [8,1], [8,2]. Sort each group by priority descending: t=7 -> [7,4], [7,3], [7,3] (ties in priority preserve original relative order); t=8 -> [8,2], [8,1]. Concatenate: [7,4], [7,3], [7,3], [8,2], [8,1].

Constraints

1 <= logs.length <= 10^5
1 <= logs[i][0] <= 10^9
1 <= logs[i][1] <= 10^9
logs[i].length == 2
The input array may contain duplicate pairs

Optimal Approach & Strategy

Use a single sorting pass with a custom comparator that compares timestamps first and only compares priorities if timestamps are equal. This leverages the O(n log n) efficiency of comparison-based sorts and handles the composite key logic in one step, ensuring correctness and optimal performance.

Brute Force Approach

Sort the array by priority in descending order, then sort the array by timestamp in ascending order. This approach is incorrect if the sort is not stable, and even if stable, it requires two full passes over the data, resulting in O(2n log n) time complexity, which is less efficient than a single composite sort.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n log n)

function solution(messages) {
   if (messages.length === 0) return [];
   return messages.sort((a, b) => {
       if (a.timestamp === b.timestamp) {
           return a.priority - b.priority;
       }
       return a.timestamp - b.timestamp;
   });
}

class Solution {
   public:
   vector<map<string, int>> solution(vector<map<string, int>> messages) {
       if (messages.empty()) return {};
       sort(messages.begin(), messages.end(), [](const map<string, int>& a, const map<string, int>& b) {
           if (a.at("timestamp") == b.at("timestamp")) {
               return a.at("priority") < b.at("priority");
           }
           return a.at("timestamp") < b.at("timestamp");
       });
       return messages;
   }
   };

class Solution {
   public Object[] solution(Object[] messages) {
       if (messages.length == 0) return new Object[0];
       Arrays.sort(messages, new Comparator<Object>() {
           @Override
           public int compare(Object o1, Object o2) {
               if (((Map) o1).get("timestamp") == ((Map) o2).get("timestamp")) {
                   return ((Integer) ((Map) o2).get("priority")) - ((Integer) ((Map) o1).get("priority"));
               }
               return ((Integer) ((Map) o1).get("timestamp")) - ((Integer) ((Map) o2).get("timestamp"));
           }
       });
       return messages;
   }
   }

def solution(messages):
   if not messages:
       return []
   return sorted(messages, key=lambda x: (x['timestamp'], -x['priority']))

function solution(messages) {
   if (messages.length === 0) return [];
   return messages.sort((a, b) => {
       if (a.timestamp === b.timestamp) {
           return a.priority - b.priority;
       }
       return a.timestamp - b.timestamp;
   });
}

Asked in Top Tech Interviews

basic-sorting-algorithmsmediumcomparison

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.

Timestamp Priority Sort Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Sorting

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Timestamp Priority Sort — 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