Python 1629.py
class Solution:
def slowestKey(self, releaseTimes: List[int], keysPressed: str) -> str:
prev = 0
longest = defaultdict(int)
for r, k in zip(releaseTimes, keysPressed):
duration = r - prev
longest[k] = max(longest[k], duration)
prev = r
result = ""
for c in "abcdefghijklmnopqrstuvwxyz":
if longest[result] <= longest[c]:
result = c
return result
Difficulty
and has an acceptance rate of about 60% (100k+ submissions).
Typical patterns to solve this problem:
- Array
- String
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided Solution class implements a method slowestKey that determines which key was held down for the longest duration given a sequence of release timestamps and the corresponding characters pressed. The algorithm processes the input in two passes: first it computes the duration of each key press and records the maximum duration observed for each distinct character; second it iterates over the alphabet in lexical order to select the character with the greatest recorded duration, breaking ties by choosing the later character alphabetically.
Key Steps
Initialisation
The method begins by setting a variable prev to zero, which represents the timestamp of the previous key release. It also creates a defaultdict named longest that maps characters to their longest observed duration, defaulting to zero for unseen keys.
prev = 0
longest = defaultdict(int)
First Pass - Duration Calculation
The core of the first pass is a loop that zips together the list of release times and the string of pressed keys. For each pair, the duration of the current press is obtained by subtracting the previous release time from the current one. The dictionary entry for the current character is updated with the larger of the existing stored duration and the newly computed duration. Finally, prev is updated to the current release time so that the next iteration can compute the subsequent interval correctly.
for r, k in zip(releaseTimes, keysPressed):
duration = r - prev
longest[k] = max(longest[k], duration)
prev = r
Second Pass - Selecting the Result
After all durations have been recorded, the method prepares an empty string result. It then iterates over the lowercase English alphabet in order. For each character c, it compares the stored duration for c with the duration associated with the current result. If the duration for c is greater than or equal to that of result, the algorithm assigns c to result. Because the loop proceeds from 'a' to 'z', a tie (equal durations) will cause the later alphabetic character to replace the earlier one, satisfying the required tie-breaking rule.
result = ""
for c in "abcdefghijklmnopqrstuvwxyz":
if longest[result] <= longest[c]:
result = c
return result
Edge Cases Handled
When the input contains only a single key press, the first loop computes the duration as releaseTimes[0] - 0, correctly handling the initial offset. The defaultdict ensures that any character not yet seen has a default duration of zero, so the comparison in the second loop never raises a KeyError.
If multiple keys share the same maximum duration, the second pass’s “less than or equal” condition guarantees that the alphabetically later key overwrites the earlier one, thereby adhering to the specification for tie resolution.
When the keysPressed string includes characters that are not present in the alphabetic range (for example, uppercase letters or symbols), the second pass simply ignores them because it only iterates over 'a' through 'z'. Consequently, only lowercase letters can be returned, which matches the expected input domain.
Performance Optimizations
The algorithm uses a single pass to compute durations, avoiding any nested loops or repeated scans of the input data. By updating the maximum duration for each character on the fly, it eliminates the need for a secondary aggregation step.
The choice of a defaultdict(int) removes the overhead of explicit existence checks before updating the dictionary, allowing the max operation to be performed directly.
The second pass iterates over a fixed 26-character alphabet rather than over the potentially larger set of distinct keys present in the input. This constant-size loop guarantees that the selection step runs in predictable time regardless of input length.
Storing only the longest duration per character, rather than all individual durations, keeps the memory footprint minimal, as the dictionary never grows beyond the number of distinct lowercase letters.
Overall, the method achieves linear processing of the input list and constant-time selection of the final answer, reflecting a design that balances clarity with efficient resource usage.
ELI5 - Simplified Explanation
Imagine a special keyboard that keeps track of how long each finger stays on a button. There is a list of times showing when each key was let go and another list showing which keys were tapped.
The computer looks at the first key press and sees how long it was held down. It remembers that time, then it looks at the next key. To know how long the second key was held, it subtracts the end time of the first key from the end time of the second key. This repeats for every button pressed.
The computer keeps a secret notepad to store the longest time each letter was held. If the letter a was held for two seconds once and then three seconds later, the computer updates the notepad to remember three.
After checking every single key, the computer looks at all the letters in the alphabet. It goes through them one by one to see which letter holds the record for the longest time. If there is a tie, it picks the letter that comes later in the alphabet.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | |||||||||
| www | AlgoMonster | C++ | Python | Java | TS | |||||
| WalkCCC | C++ | Python | Java | |||||||
| leetcode.ca | C++ | Python | Java | Go | ||||||
| Progiez | C++ | Python | Java | |||||||
| github | black-shadows | C++ | ||||||||
| charles-wangkai | Java | |||||||||
| DimitrisJim | C | |||||||||
| everthis | JS | |||||||||
| fartem | Ruby | |||||||||
| fpdjsns | C++ | |||||||||
| fsq | C++ | |||||||||
| halfrost | Go | |||||||||
| JoshCrozier | JS | |||||||||
| lkwq007 | Python | |||||||||
| suxrobGM | C# | |||||||||
| trung-hn | Python | |||||||||
| varunu28 | Java | |||||||||
| YuriSpiridonov | Python | |||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||
| WalkCCC | C++, Python, Java | |||||||||
| leetcode.ca | C++, Go, Java, Python | |||||||||
| Progiez | C++, Java, Python | |||||||||
| black-shadows | C++, C++ | |||||||||
| charles-wangkai | Java | |||||||||
| DimitrisJim | C | |||||||||
| everthis | JavaScript | |||||||||
| fartem | Ruby | |||||||||
| fpdjsns | C++ | |||||||||
| fsq | C++ | |||||||||
| halfrost | Go | |||||||||
| JoshCrozier | JavaScript | |||||||||
| lkwq007 | Python | |||||||||
| suxrobGM | C# | |||||||||
| trung-hn | Python | |||||||||
| varunu28 | Java | |||||||||
| YuriSpiridonov | Python |
Videos
Solved On The Same Day
- problem 1550: Three Consecutive Odds
- problem 1637: Widest Vertical Area Between Two Points Containing No Points
- problem 1684: Count the Number of Consistent Strings
- problem 1630: Arithmetic Subarrays
- problem 1663: Smallest String With A Given Numeric Value
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality