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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Button with Longest Push Time

Number: 3632

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an array of events where each event is represented as [button index, time] and the array is sorted by time, determine the button that experienced the longest push duration. The first event's duration is its own time, and for every subsequent event, the duration is the difference between the current event's time and the previous event's time. In case of a tie, return the button with the smallest index.

Key Insights

  • The events are already sorted by time; hence, a single pass solution is possible.
  • The duration for the first event is the event time itself.
  • For every subsequent event, the push time is computed as the time difference between the current event and the previous event.
  • Track the maximum duration and update the corresponding button index, taking into account the tie-breaking rule (smallest index wins).

Space and Time Complexity

Time Complexity: O(n), where n is the number of events. Space Complexity: O(1), using constant extra space.

Solution

We use a single pass through the events array. First, initialize the maximum duration using the first event’s time and record its button index. Then, for each subsequent event, calculate the duration by subtracting the previous event's time from the current event's time. Update the maximum duration and associated button index when a longer duration is found. In case a duration equals the current maximum, update the button index only if the current button index is smaller than the existing one.

Code Solutions

def longestPushTime(events):
    # Initialize max push time with the first event's time
    max_duration = events[0][1]
    result_button = events[0][0]
    
    # Iterate from the second event onward to calculate durations
    for i in range(1, len(events)):
        duration = events[i][1] - events[i-1][1]  # Duration between current and previous event
        if duration > max_duration:
            max_duration = duration
            result_button = events[i][0]
        elif duration == max_duration and events[i][0] < result_button:
            result_button = events[i][0]
    
    return result_button

# Example usage:
print(longestPushTime([[1,2],[2,5],[3,9],[1,15]]))  # Output: 1
← Back to All Questions