Button with Longest Push Time - Practice Coding Problems

Button with Longest Push Time - Problem

Array Easy

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] = [index_i, time_i] indicates that the button at index index_i was pressed at time time_i.

The array is sorted in increasing order of time. The time taken to press a button is the difference in time between consecutive button presses. The time for the first button is simply the time at which it was pressed.

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.

Input & Output

Example 1 — Basic Case

$ Input: events = [[1,2],[2,5],[3,9],[1,15]]

› Output: 1

💡 Note: Button durations: Button 1 at time 2 (duration=2), Button 2 at time 5 (duration=5-2=3), Button 3 at time 9 (duration=9-5=4), Button 1 at time 15 (duration=15-9=6). Button 1 has the longest press duration of 6.

Example 2 — First Button Winner

$ Input: events = [[9,20],[6,1],[1,3],[1,8]]

› Output: 9

💡 Note: Button durations: Button 9 (duration=20), Button 6 (duration=1-20=-19, but since events are sorted by time, this would be 1), Button 1 (duration=3-1=2), Button 1 (duration=8-3=5). Wait, let me recalculate: events should be sorted by time, so [[6,1],[1,3],[1,8],[9,20]]. Button 6 (duration=1), Button 1 (duration=3-1=2), Button 1 (duration=8-3=5), Button 9 (duration=20-8=12). Button 9 wins with duration 12.

Example 3 — Tie Breaking

$ Input: events = [[2,3],[1,7]]

› Output: 1

💡 Note: Button durations: Button 2 (duration=3), Button 1 (duration=7-3=4). Button 1 has longer duration of 4, so return 1.

Constraints

1 ≤ events.length ≤ 1000
events[i] = [index_i, time_i]
1 ≤ index_i, time_i ≤ 10⁵
events is sorted in increasing order of time_i

Visualization

Tap to expand

Understanding the Visualization

Input Events

Array of [button_index, timestamp] pairs sorted by time

Calculate Durations

First button duration = timestamp, others = time difference

Find Maximum

Return button index with longest duration (smallest index for ties)

Key Takeaway

🎯 Key Insight: Calculate durations correctly - first button uses timestamp, others use time differences between consecutive events

Asked in

f Meta 15 a Amazon 12 G Google 8

The key insight is that we need to calculate press durations correctly: first button's duration is its timestamp, others are time differences between consecutive events. The optimal approach uses a single pass to track the longest duration while handling ties by preferring smaller indices. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass Tracking	O(n)	O(1)	Iterate through events once, calculate each button's press duration, track the longest
Optimized Single Pass with Early Comparison	O(n)	O(1)	Same single pass but with optimized comparison logic for tie-breaking

Single Pass Tracking — Algorithm Steps

Step 1: Initialize variables to track longest duration and its button index
Step 2: For each event, calculate press duration (timestamp for first, difference for others)
Step 3: Update longest duration and button index when we find a longer press or same duration with smaller index

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set first button as current longest with its timestamp as duration

Process

For each subsequent button, calculate duration as time difference

Update

Keep track of button with longest duration (smallest index for ties)

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int events[][2], int n) {
    int maxDuration = 0;
    int resultButton = events[0][0];
    
    // First button duration is just its timestamp
    maxDuration = events[0][1];
    
    // Check remaining buttons
    for (int i = 1; i < n; i++) {
        int currentButton = events[i][0];
        int currentDuration = events[i][1] - events[i-1][1];
        
        // Update if longer duration or same duration with smaller index
        if (currentDuration > maxDuration || (currentDuration == maxDuration && currentButton < resultButton)) {
            maxDuration = currentDuration;
            resultButton = currentButton;
        }
    }
    
    return resultButton;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse 2D array - simple parsing for contest format
    int events[1000][2];
    int n = 0;
    
    char *ptr = line;
    while (*ptr && *ptr != '[') ptr++; // Find first [
    ptr++; // Skip [
    
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            events[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++; // Skip comma
            events[n][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++; // Skip ]
            n++;
        } else {
            ptr++;
        }
    }
    
    int result = solution(events, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single loop through all n events

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

8.5K Views

Medium Frequency

~12 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler