We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Button with Longest Push Time

Difficulty: Easy

Problem Description

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.

Key Insights

  • The first button press sets the initial time for that button.
  • The time taken to press a button is calculated as the difference between the current button press time and the previous button press time.
  • We need to keep track of the maximum push time for each button and the corresponding index.
  • If two buttons have the same maximum time, return the button with the smallest index.

Space and Time Complexity

Time Complexity: O(n), where n is the number of events. Each event is processed once.
Space Complexity: O(m), where m is the number of unique buttons. This space is used to store the time taken for each button.

Solution

We can use a dictionary to store the total time taken for each button. We will iterate through the events, calculate the time taken for each button based on the previous event's time, and update the dictionary accordingly. At the end, we will determine which button has the longest time and return its index.

Code Solutions

def button_with_longest_push_time(events):
    push_times = {}
    last_time = {}
    
    for index, time in events:
        if index not in last_time:
            # First press of the button
            time_taken = time
        else:
            # Time taken since the last press
            time_taken = time - last_time[index]
        
        # Update the last press time for the button
        last_time[index] = time
        
        # Update the total time taken for this button
        if index in push_times:
            push_times[index] += time_taken
        else:
            push_times[index] = time_taken
    
    # Find the button with the longest push time
    max_time = -1
    button_index = float('inf')
    
    for index, total_time in push_times.items():
        if total_time > max_time or (total_time == max_time and index < button_index):
            max_time = total_time
            button_index = index
            
    return button_index
← Back to All Questions