LeetCode 1629 - Slowest Key

Difficulty: 🟢 Easy
Topics: Array, String

Solution

Problem Understanding

This problem asks us to determine which key on a keypad was pressed for the longest duration during a test sequence. We are given two pieces of information: a list of releaseTimes indicating when each key was released, and a string keysPressed representing the keys pressed in order. The first key is considered pressed at time 0, and each subsequent key is pressed exactly when the previous one is released.

The duration of a keypress is calculated as the difference between its release time and the previous key's release time, except for the first key, which has a duration equal to its release time. If multiple keypresses have the same maximum duration, we must return the lexicographically largest key.

The constraints tell us the input length n is small (up to 1000), the release times are strictly increasing, and only lowercase English letters are used for keys. This guarantees no ties in timing except for multiple keypresses having the same duration, and the arrays are always valid. Important edge cases include the first key being the slowest and ties between durations that require lexicographical comparison.

Approaches

The brute-force approach would iterate over each keypress, compute its duration, and store the maximum duration along with the key. This works correctly and is efficient for n = 1000, but we must carefully handle ties using lexicographical comparison. There is no faster asymptotic solution because we must examine every key at least once, so a single-pass iteration is optimal.

The key observation is that we can track the maximum duration on the fly. While iterating through the keypresses, we compare the current key's duration with the maximum found so far. If the duration is greater, we update the max and the corresponding key. If the duration is equal to the max, we update the key only if it is lexicographically larger. This gives an O(n) solution in a single pass with constant extra space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Compute durations for all keys and track max in a list, then select max with lexicographical tie-breaking
Optimal	O(n)	O(1)	Single pass tracking max duration and lexicographically largest key

Algorithm Walkthrough

Initialize maxDuration as the duration of the first keypress (releaseTimes[0]) and resultKey as keysPressed[0].
Iterate through the rest of the keypresses from index 1 to n-1.
For each key at index i, calculate its duration as releaseTimes[i] - releaseTimes[i-1].
If this duration is greater than maxDuration, update maxDuration and set resultKey to the current key.
If the duration equals maxDuration, update resultKey only if the current key is lexicographically larger than the current resultKey.
After processing all keypresses, return resultKey.

Why it works: The algorithm maintains the invariant that after each iteration, resultKey is the key with the longest duration seen so far, or the lexicographically largest key among those tied for the longest duration. This ensures correctness with a single pass.

Python Solution

from typing import List

class Solution:
    def slowestKey(self, releaseTimes: List[int], keysPressed: str) -> str:
        maxDuration = releaseTimes[0]
        resultKey = keysPressed[0]
        
        for i in range(1, len(keysPressed)):
            duration = releaseTimes[i] - releaseTimes[i - 1]
            if duration > maxDuration or (duration == maxDuration and keysPressed[i] > resultKey):
                maxDuration = duration
                resultKey = keysPressed[i]
                
        return resultKey

The Python implementation directly follows the algorithm walkthrough. We initialize the maximum duration and result key with the first key, then iterate through the remaining keys. For each key, we compute its duration relative to the previous key. If the duration exceeds the current maximum, we update both maxDuration and resultKey. If the duration ties the maximum, we perform a lexicographical comparison to decide whether to update resultKey.

Go Solution

func slowestKey(releaseTimes []int, keysPressed string) byte {
    maxDuration := releaseTimes[0]
    resultKey := keysPressed[0]
    
    for i := 1; i < len(keysPressed); i++ {
        duration := releaseTimes[i] - releaseTimes[i-1]
        if duration > maxDuration || (duration == maxDuration && keysPressed[i] > resultKey) {
            maxDuration = duration
            resultKey = keysPressed[i]
        }
    }
    
    return resultKey
}

The Go solution mirrors the Python approach. We initialize the maximum duration and result key using the first key, iterate through the keys, and update accordingly. Go handles string indexing as bytes, which aligns perfectly with the lexicographical comparison using the > operator.

Worked Examples

Example 1

Input: releaseTimes = [9,29,49,50], keysPressed = "cbcd"

i	Key	Duration	maxDuration	resultKey
0	c	9	9	c
1	b	20	20	b
2	c	20	20	c (lexicographically larger than b)
3	d	1	20	c

Output: "c"

Example 2

Input: releaseTimes = [12,23,36,46,62], keysPressed = "spuda"

i	Key	Duration	maxDuration	resultKey
0	s	12	12	s
1	p	11	12	s
2	u	13	13	u
3	d	10	13	u
4	a	16	16	a

Output: "a"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass over all `n` keypresses, each operation is O(1)
Space	O(1)	Only a few variables for max duration and result key are used

This is optimal given we must examine each keypress at least once.

Test Cases

# Provided examples
assert Solution().slowestKey([9,29,49,50], "cbcd") == "c"  # tie with lexicographical resolution
assert Solution().slowestKey([12,23,36,46,62], "spuda") == "a"  # longest duration at the end

# Edge cases
assert Solution().slowestKey([1,2], "ab") == "b"  # shortest sequence
assert Solution().slowestKey([5,10,15], "aaa") == "a"  # all keys same
assert Solution().slowestKey([2,5,9,10], "bdca") == "d"  # middle key longest
assert Solution().slowestKey([1,3,3,3], "abcd") == "b"  # tie for duration with lexicographical tie-break

# Large values
assert Solution().slowestKey([1,1000000000], "az") == "z"  # large difference, last key longest

Test	Why
Shortest sequence	Ensures algorithm works for minimum n
All keys same	Ensures lexicographical tie-break is not required when keys are identical
Middle key longest	Checks that algorithm correctly identifies non-first/non-last maximum
Tie for duration	Validates correct lexicographical tie-break
Large values	Ensures algorithm handles large integers correctly

Edge Cases

One important edge case is when the first key is the slowest. Since its duration is calculated differently (releaseTimes[0]), a naive implementation that always uses releaseTimes[i] - releaseTimes[i-1] for all keys may miscalculate the first duration. This implementation correctly initializes maxDuration with releaseTimes[0].

Another edge case is ties in duration. Multiple keys may have the same duration, and the problem requires returning the lexicographically largest key. This is handled with a simple comparison keysPressed[i] > resultKey whenever the duration equals maxDuration.

A third edge case is all keys the same. If every key pressed is identical, the longest duration key is naturally that key, but the algorithm must still compute durations correctly rather than relying on key uniqueness. This is handled seamlessly by the iteration and comparisons.