Button with Longest Push Time — Problem & Solution
Button with Longest Push Time solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays.
Button with Longest Push Time is an easy coding problem on arrays, asked in Amazon interviews.
- Difficulty: Easy
- Topics: Arrays
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A keypad logs every button press as presses[i] = [index, time]: button index was pressed at moment time. The log is sorted by time in strictly increasing order.
The time a press took is the gap since the previous press — time[i] - time[i - 1] — and for the very first press it is simply time[0].
Return the index of the button whose single press took the longest. If several presses tie for the longest, return the smallest button index among them.
Example 1
Input: presses = [[1,2],[2,5],[3,9],[1,15]]
Output: 1
Explanation: The presses took 2, 3, 4 and 6 units; the longest (6) was button 1.
Example 2
Input: presses = [[10,5],[1,7]]
Output: 10
Explanation: Button 10 took 5 and button 1 took 2.
Example 3
Input: presses = [[3,1],[2,4],[1,7]]
Output: 1
Explanation: Buttons 2 and 1 both took 3 units — the smaller index wins.
Constraints
1 <= presses.length <= 1000presses[i].length == 21 <= index, time <= 10^5presses is sorted by time in strictly increasing order
Hints for Button with Longest Push Time
Hint 1
Each press's duration only depends on its own time and the previous press's time.
Hint 2
Scan once, computing each duration and keeping the best duration seen with its button index.
Hint 3
On a tie, keep the smaller index — the same button can appear many times, so compare indices, not positions.
How to solve Button with Longest Push Time
Compute each press's duration in one pass — time for the first press, the gap to the previous press otherwise — and keep the longest, breaking ties by the smaller button index.
Approach
- Set
bestTime = -1,bestIdx = -1,prev = 0. - For each press
[idx, t]:d = t - prev(withprev = 0this givestfor the first press). - If
d > bestTime, ord == bestTimeandidx < bestIdx, setbestTime = d,bestIdx = idx. Thenprev = t. - Return
bestIdx.
Why it works
Every press's duration is examined exactly once and the comparison implements the required order (longer first, then smaller index), so the final state is the required button.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The first press's duration is its own time, not zero.
- The tie-break is on the button
index, not on which press came first.
Reference solution
Python
from typing import List
def buttonWithLongestTime(presses: List[List[int]]) -> int:
best_time, best_idx, prev = -1, -1, 0
for idx, t in presses:
d = t - prev
if d > best_time or (d == best_time and idx < best_idx):
best_time, best_idx = d, idx
prev = t
return best_idxJava
public static int buttonWithLongestTime(int[][] presses) {
int bestTime = -1, bestIdx = -1, prev = 0;
for (int[] p : presses) {
int d = p[1] - prev;
if (d > bestTime || (d == bestTime && p[0] < bestIdx)) { bestTime = d; bestIdx = p[0]; }
prev = p[1];
}
return bestIdx;
}C++
int buttonWithLongestTime(vector<vector<int>>& presses) {
int bestTime = -1, bestIdx = -1, prev = 0;
for (auto& p : presses) {
int d = p[1] - prev;
if (d > bestTime || (d == bestTime && p[0] < bestIdx)) { bestTime = d; bestIdx = p[0]; }
prev = p[1];
}
return bestIdx;
}JavaScript
var buttonWithLongestTime = function(presses) {
var bestTime = -1, bestIdx = -1, prev = 0;
for (var i = 0; i < presses.length; i++) {
var idx = presses[i][0], t = presses[i][1];
var d = t - prev;
if (d > bestTime || (d === bestTime && idx < bestIdx)) { bestTime = d; bestIdx = idx; }
prev = t;
}
return bestIdx;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays