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

Slowest Key

Number: 1751

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given a sequence of keys pressed and the corresponding release times, determine which key had the longest press duration. The duration of the very first key is its releaseTime, and for every subsequent key, it is the difference between its releaseTime and that of the previous key. In the event of a tie in duration, return the lexicographically largest key.

Key Insights

  • The first key's duration is directly provided by releaseTimes[0].
  • For every other key, the duration is calculated as releaseTimes[i] - releaseTimes[i - 1].
  • Tracking the maximum duration and updating the result with lexicographic comparison when durations are equal ensures we get the correct answer.
  • A simple iteration over the arrays is sufficient to solve the problem.

Space and Time Complexity

Time Complexity: O(n) where n is the number of keypresses. Space Complexity: O(1) since only a few variables are used.

Solution

We iterate through the releaseTimes list while simultaneously accessing the keys in keysPressed. For the first key, the duration is just its release time. For the following keys, the duration is computed as the difference between the current and previous release times. As we iterate, we maintain two variables: one to track the maximum duration encountered so far, and another to store the key corresponding to that duration. If we find a keypress that has a duration equal to the current maximum, we then check if its key is lexicographically larger than the one stored, and update accordingly. This approach ensures that we satisfy the condition for ties.

Code Solutions

# Python solution
def slowestKey(releaseTimes, keysPressed):
    # Initialize maximum duration with the first key's press duration
    max_duration = releaseTimes[0]
    # The result key is initially the first key pressed
    slowest_key = keysPressed[0]
    
    # Iterate through the list starting from the second key
    n = len(releaseTimes)
    for i in range(1, n):
        # Calculate duration for the current key press
        duration = releaseTimes[i] - releaseTimes[i - 1]
        # Check if the current duration exceeds the maximum duration found so far
        if duration > max_duration:
            max_duration = duration
            slowest_key = keysPressed[i]
        # If durations are equal, choose the lexicographically larger key
        elif duration == max_duration and keysPressed[i] > slowest_key:
            slowest_key = keysPressed[i]
    
    return slowest_key

# Example usage:
print(slowestKey([9,29,49,50], "cbcd"))  # Output: "c"
← Back to All Questions