You are given a 2D array events which represents a sequence of events where a child pushes a series of buttons on a keyboard.
Each events[i] = [indexi, timei] indicates that the button at index indexi was pressed at time timei.
time.Return the index of the button that took the longest time to push. If multiple buttons have the same longest time, return the button with the smallest index.
Example 1:
Input: events = [[1,2],[2,5],[3,9],[1,15]]
Output: 1
Explanation:
5 - 2 = 3 units of time.9 - 5 = 4 units of time.15 - 9 = 6 units of time.Example 2:
Input: events = [[10,5],[1,7]]
Output: 10
Explanation:
7 - 5 = 2 units of time.
Constraints:
1 <= events.length <= 1000events[i] == [indexi, timei]1 <= indexi, timei <= 105events is sorted in increasing order of timei.Problem Overview: You are given a list of button press events where each entry contains a button ID and the time the press ended. The duration of a press is the difference between the current timestamp and the previous one. Your task is to determine which button had the longest push duration.
Approach 1: Brute Force Duration Recalculation (O(n^2) time, O(1) space)
A naive approach recomputes durations by scanning backward for every event to determine when the previous press ended. For each index i, calculate the push duration and compare it with the current maximum. This repeatedly revisits earlier entries, leading to unnecessary work. The idea works but scales poorly because every event may trigger another scan of the array.
This approach demonstrates the core insight: the push time is simply the difference between consecutive timestamps. Once you recognize that durations only depend on the previous event, the quadratic work becomes unnecessary.
Approach 2: Single Pass Duration Tracking (O(n) time, O(1) space)
The optimal solution iterates through the event log once. The duration of the first press equals its timestamp because it starts at time 0. For every subsequent event, compute the duration using logs[i][1] - logs[i-1][1]. Track the maximum duration seen so far and update the result when a longer press appears.
If two presses share the same duration, choose the smaller button ID to maintain deterministic output. The algorithm only keeps a few variables: previous timestamp, current duration, and the best button so far. Because the data is already ordered by time, a single forward iteration over the array is enough. This pattern is common in simulation-style problems where events occur sequentially.
Recommended for interviews: Interviewers expect the single-pass solution. The brute force explanation shows you understand how durations are derived, but the optimal approach demonstrates that you can reduce redundant work and exploit sequential ordering. Recognizing that each event only depends on the previous one leads directly to the O(n) scan.
We define two variables ans and t, representing the index of the button with the longest press time and the press time, respectively.
Next, we start traversing the array events from index k = 1. For each k, we calculate the press time of the current button d = t2 - t1, where t2 is the press time of the current button and t1 is the press time of the previous button. If d > t or d = t and the index i of the current button is less than ans, we update ans = i and t = d.
Finally, we return ans.
The time complexity is O(n), where n is the length of the array events. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Duration Recalculation | O(n^2) | O(1) | Conceptual understanding of duration calculation; not practical for large inputs |
| Single Pass Duration Tracking | O(n) | O(1) | Optimal approach when events are already sorted by time |
3386. Button with Longest Push Time (Leetcode Easy) • Programming Live with Larry • 298 views views
Watch 5 more video solutions →Practice Button with Longest Push Time with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor