Leetcode – Slowest Key Solution

Spread the love

The “Slowest Key” problem on Leetcode serves as an excellent illustration of how array and string manipulation can be used to solve real-world problems. At the core, it’s a problem about determining the slowest keypress given the time taken to release each key. Despite its seemingly simple premise, this problem challenges one to think carefully about edge cases and optimization.

In this comprehensive article, we’ll deconstruct the problem description, explore various approaches to solving the problem, analyze their time and space complexity, and finally, implement them in Python.

Problem Description

The problem statement on Leetcode is as follows:

A newly designed keypad was tested, where a tester pressed a sequence of n keys, one at a time. You are given a string keysPressed of length n, where keysPressed[i] was the i-th key pressed in the testing sequence, and a sorted list releaseTimes, where releaseTimes[i] was the time the i-th key was released. Both arrays are 0-indexed. The 0-th key was pressed at the time 0, and every subsequent key was pressed at the exact time the previous key was released.

The tester wants to know the key of the keypress that had the longest duration. The i-th keypress had a duration of releaseTimes[i] - releaseTimes[i - 1] for every i > 0, and the 0-th keypress had a duration of releaseTimes[0].

Note that the same key could have been pressed multiple times during the test, and these multiple presses of the same key may not have had the same duration.

Example

slowestKey([9, 29, 49, 50], "cbcd")  # Output: "c"

Approach 1: Iterative Comparison

Algorithm

  1. Initialize variables max_duration and slowest_key to store the maximum keypress duration and the corresponding key.
  2. Traverse the releaseTimes array and keysPressed string together to calculate the duration for each keypress.
  3. Update max_duration and slowest_key whenever a larger duration is found. If the duration is the same but the key is lexicographically larger, update slowest_key.

Python Code

from typing import List

def slowestKey(releaseTimes: List[int], keysPressed: str) -> str:
    max_duration = releaseTimes[0]
    slowest_key = keysPressed[0]
    
    for i in range(1, len(releaseTimes)):
        duration = releaseTimes[i] - releaseTimes[i - 1]
        key = keysPressed[i]
        
        if duration > max_duration or (duration == max_duration and key > slowest_key):
            max_duration = duration
            slowest_key = key
            
    return slowest_key

Time Complexity

The time complexity of this approach is O(n), where n is the length of the releaseTimes array or keysPressed string.

Space Complexity

The space complexity is O(1) as we are not using any additional data structures.

Approach 2: Using Enumerate Function (Pythonic Way)

This approach is not fundamentally different from the first one but uses Python’s built-in enumerate function for more concise code.

Python Code

def slowestKey(releaseTimes: List[int], keysPressed: str) -> str:
    max_duration = releaseTimes[0]
    slowest_key = keysPressed[0]
    
    for i, (time, key) in enumerate(zip(releaseTimes[1:], keysPressed[1:])):
        duration = time - releaseTimes[i]
        
        if duration > max_duration or (duration == max_duration and key > slowest_key):
            max_duration = duration
            slowest_key = key
            
    return slowest_key

Conclusion

The “Slowest Key” problem is a simple yet insightful exercise in array and string manipulation. The two approaches discussed offer a trade-off between readability and traditional loop structure, but both are optimal in terms of time and space complexity. This problem serves as an excellent starting point for those looking to strengthen their skills in string and array manipulation, preparing them for more complex challenges in coding interviews and beyond.

Leave a Reply