LeetCode 3386 - Button with Longest Push Time

The problem gives us a sequence of keyboard button press events. Each event is represented as: Here: - index is the identifier of the button that was pressed. - time is the moment when the press happened.

leetcodeeasyarray

LeetCode Problem 3386

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

The problem gives us a sequence of keyboard button press events. Each event is represented as:

[index, time]

Here:

  • index is the identifier of the button that was pressed.
  • time is the moment when the press happened.

The events are already sorted by increasing time, which is extremely important because it means we can process the presses in chronological order without additional sorting.

The duration of a button press is defined differently for the first event versus later events:

  • For the first button press, the duration is simply its timestamp.
  • For every other button press, the duration is the difference between the current timestamp and the previous timestamp.

Our goal is to determine which button had the largest press duration.

If multiple buttons share the same maximum duration, we must return the smallest button index among them.

For example, consider:

[[1,2],[2,5],[3,9],[1,15]]

The durations become:

  • Button 1: 2
  • Button 2: 5 - 2 = 3
  • Button 3: 9 - 5 = 4
  • Button 1: 15 - 9 = 6

The largest duration is 6, so the answer is button 1.

The constraints are very small:

  • At most 1000 events
  • Time values up to 10^5

Because the input size is small, even less efficient approaches would pass. However, the problem is fundamentally simple enough that we can solve it optimally in a single pass.

Several edge cases are important:

  • A single event array, where the first event is automatically the answer.
  • Multiple buttons having the same maximum duration, requiring tie-breaking by smaller index.
  • Large timestamp gaps between consecutive events.
  • Repeated presses of the same button.

The problem guarantees that timestamps are strictly increasing because the events are sorted by time.

Approaches

Brute Force Approach

A brute force approach would explicitly compute the duration for every event and store all durations in a separate list or map. After building this collection, we would scan through it again to determine the maximum duration and apply the tie-breaking rule.

This works because every button press duration can be computed independently using the previous timestamp. Once all durations are known, selecting the best candidate becomes straightforward.

However, this approach performs unnecessary extra work because we do not actually need to store every duration before deciding the answer. We can determine the best candidate while processing the events.

Although the constraints are small enough that this solution would still pass, it uses extra memory and requires additional traversal.

Optimal Approach

The key observation is that we only need to know:

  • The best duration seen so far
  • The corresponding button index
  • The previous timestamp

As we iterate through the events once, we can immediately compute the current duration:

current_duration = current_time - previous_time

For the first event, the duration is simply its timestamp.

After computing the duration, we compare it against the current maximum:

  • If the duration is larger, update the answer.
  • If the duration is equal and the current index is smaller, also update the answer.

Because every event is processed exactly once and no additional data structures are required, this produces an optimal linear-time solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Stores all durations before determining the answer
Optimal O(n) O(1) Single pass while maintaining current best result

Algorithm Walkthrough

  1. Initialize the answer using the first event.

The first event is special because its duration equals its timestamp. Set:

  • max_duration = events[0][1]
  • answer = events[0][0]
  1. Start iterating from the second event.

For each event:

  • Extract the current button index and timestamp.
  • Compute the duration as:
current_time - previous_time
  1. Compare the current duration against the best duration seen so far.

There are two cases where we update the answer:

  • The current duration is larger than max_duration
  • The current duration equals max_duration and the current button index is smaller
  1. Update the tracking variables.

If the current event becomes the new best candidate:

  • Update max_duration
  • Update answer
  1. Continue until all events are processed.
  2. Return the final answer.

Why it works

The algorithm maintains an invariant throughout the iteration:

  • After processing each event, max_duration stores the largest duration encountered so far.
  • answer stores the smallest index among all buttons achieving that duration.

Since every event duration is computed exactly once and compared immediately against the current best candidate, the algorithm guarantees that the final answer satisfies both the maximum-duration requirement and the tie-breaking rule.

Python Solution

from typing import List

class Solution:
    def buttonWithLongestTime(self, events: List[List[int]]) -> int:
        max_duration = events[0][1]
        answer = events[0][0]

        for i in range(1, len(events)):
            current_index = events[i][0]
            current_time = events[i][1]

            previous_time = events[i - 1][1]
            duration = current_time - previous_time

            if duration > max_duration:
                max_duration = duration
                answer = current_index
            elif duration == max_duration and current_index < answer:
                answer = current_index

        return answer

The implementation begins by handling the first event separately because its duration is simply its timestamp.

The variables max_duration and answer track the best result found so far.

The loop starts from index 1 because every later event computes its duration relative to the previous event. For each iteration:

  • The current button index and timestamp are extracted.
  • The duration is computed using the previous timestamp.
  • The algorithm compares the duration against the current maximum.

The tie-breaking rule is handled explicitly in the elif condition. If two buttons have the same duration, the smaller button index becomes the answer.

Finally, the method returns the stored answer after processing all events.

Go Solution

func buttonWithLongestTime(events [][]int) int {
    maxDuration := events[0][1]
    answer := events[0][0]

    for i := 1; i < len(events); i++ {
        currentIndex := events[i][0]
        currentTime := events[i][1]

        previousTime := events[i-1][1]
        duration := currentTime - previousTime

        if duration > maxDuration {
            maxDuration = duration
            answer = currentIndex
        } else if duration == maxDuration && currentIndex < answer {
            answer = currentIndex
        }
    }

    return answer
}

The Go implementation follows the same logic as the Python version.

Slices are used for the events input, and integer arithmetic is straightforward because the constraints are small enough that integer overflow is not a concern. Go does not require special handling for empty input because the problem guarantees at least one event.

Worked Examples

Example 1

Input:

events = [[1,2],[2,5],[3,9],[1,15]]

Initial state:

Variable Value
max_duration 2
answer 1

Process remaining events:

i Current Event Duration max_duration answer Action
1 [2,5] 5 - 2 = 3 3 2 New maximum
2 [3,9] 9 - 5 = 4 4 3 New maximum
3 [1,15] 15 - 9 = 6 6 1 New maximum

Final answer:

1

Example 2

Input:

events = [[10,5],[1,7]]

Initial state:

Variable Value
max_duration 5
answer 10

Process remaining events:

i Current Event Duration max_duration answer Action
1 [1,7] 7 - 5 = 2 5 10 No update

Final answer:

10

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each event is processed exactly once
Space O(1) Only a few variables are maintained

The algorithm performs a single traversal through the input array. No auxiliary data structures proportional to input size are used, so the extra space remains constant.

Test Cases

from typing import List

class Solution:
    def buttonWithLongestTime(self, events: List[List[int]]) -> int:
        max_duration = events[0][1]
        answer = events[0][0]

        for i in range(1, len(events)):
            current_index = events[i][0]
            current_time = events[i][1]

            previous_time = events[i - 1][1]
            duration = current_time - previous_time

            if duration > max_duration:
                max_duration = duration
                answer = current_index
            elif duration == max_duration and current_index < answer:
                answer = current_index

        return answer

solution = Solution()

assert solution.buttonWithLongestTime([[1,2],[2,5],[3,9],[1,15]]) == 1
# Basic example with increasing durations

assert solution.buttonWithLongestTime([[10,5],[1,7]]) == 10
# First button remains the longest

assert solution.buttonWithLongestTime([[5,3]]) == 5
# Single event case

assert solution.buttonWithLongestTime([[1,2],[2,4],[3,6]]) == 1
# All durations equal, choose smallest index

assert solution.buttonWithLongestTime([[3,4],[2,8],[1,12]]) == 1
# Equal maximum durations later, tie broken by smaller index

assert solution.buttonWithLongestTime([[8,1],[9,100]]) == 9
# Very large duration gap

assert solution.buttonWithLongestTime([[4,5],[4,10],[4,20]]) == 4
# Same button pressed repeatedly

assert solution.buttonWithLongestTime([[9,2],[1,5],[2,9],[3,14]]) == 3
# Maximum duration appears at the end
Test Why
[[1,2],[2,5],[3,9],[1,15]] Validates normal multi-event processing
[[10,5],[1,7]] Ensures first event can remain the answer
[[5,3]] Validates single-event handling
[[1,2],[2,4],[3,6]] Tests tie-breaking by smallest index
[[3,4],[2,8],[1,12]] Tests repeated equal maximum durations
[[8,1],[9,100]] Tests very large time differences
[[4,5],[4,10],[4,20]] Tests repeated presses of the same button
[[9,2],[1,5],[2,9],[3,14]] Tests maximum duration occurring late

Edge Cases

Single Event

If the input contains only one event, there is no previous timestamp to subtract from. A naive implementation might accidentally skip processing or attempt an invalid subtraction.

This implementation handles the case naturally by initializing the answer using the first event before entering the loop. Since the loop starts at index 1, it never executes for a single-element input.

Multiple Buttons With Equal Maximum Duration

Tie-breaking is one of the most common sources of bugs in this problem. An implementation that only updates when a strictly larger duration appears would fail cases where multiple buttons share the same maximum duration.

The solution explicitly checks:

elif duration == max_duration and current_index < answer:

This guarantees the smallest index is selected whenever durations tie.

Maximum Duration Occurs on the First Event

Some implementations incorrectly assume the first event cannot be the answer because later durations are computed using differences between timestamps.

However, the first event's duration is defined as its own timestamp. Initializing max_duration with events[0][1] ensures the first event is fully considered in the comparison process.