LeetCode #1629 — EASY

Slowest Key

Build confidence with an intuition-first walkthrough focused on array fundamentals.

The Problem

Problem Statement

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^thkeypress had a duration of releaseTimes[i] - releaseTimes[i - 1], 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.

Return the key of the keypress that had the longest duration. If there are multiple such keypresses, return the lexicographically largest key of the keypresses.

Example 1:

Input: releaseTimes = [9,29,49,50], keysPressed = "cbcd"
Output: "c"
Explanation: The keypresses were as follows:
Keypress for 'c' had a duration of 9 (pressed at time 0 and released at time 9).
Keypress for 'b' had a duration of 29 - 9 = 20 (pressed at time 9 right after the release of the previous character and released at time 29).
Keypress for 'c' had a duration of 49 - 29 = 20 (pressed at time 29 right after the release of the previous character and released at time 49).
Keypress for 'd' had a duration of 50 - 49 = 1 (pressed at time 49 right after the release of the previous character and released at time 50).
The longest of these was the keypress for 'b' and the second keypress for 'c', both with duration 20.
'c' is lexicographically larger than 'b', so the answer is 'c'.

Example 2:

Input: releaseTimes = [12,23,36,46,62], keysPressed = "spuda"
Output: "a"
Explanation: The keypresses were as follows:
Keypress for 's' had a duration of 12.
Keypress for 'p' had a duration of 23 - 12 = 11.
Keypress for 'u' had a duration of 36 - 23 = 13.
Keypress for 'd' had a duration of 46 - 36 = 10.
Keypress for 'a' had a duration of 62 - 46 = 16.
The longest of these was the keypress for 'a' with duration 16.

Constraints:

releaseTimes.length == n
keysPressed.length == n
2 <= n <= 1000
1 <= releaseTimes[i] <= 10⁹
releaseTimes[i] < releaseTimes[i+1]
keysPressed contains only lowercase English letters.

Step 01

Brute Force Baseline

Problem summary: 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 ith key pressed in the testing sequence, and a sorted list releaseTimes, where releaseTimes[i] was the time the ith key was released. Both arrays are 0-indexed. The 0th 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 ith keypress had a duration of releaseTimes[i] - releaseTimes[i - 1], and the 0th 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. Return the key of the keypress that had the longest duration. If there

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array

Example 1

[9,29,49,50]
"cbcd"

Example 2

[12,23,36,46,62]
"spuda"

Step 02

Core Insight

What unlocks the optimal approach

Get for each press its key and amount of time taken.
Iterate on the presses, maintaining the answer so far.
The current press will change the answer if and only if its amount of time taken is longer than that of the previous answer, or they are equal but the key is larger than that of the previous answer.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Upper-end input sizes

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #1629: Slowest Key
class Solution {
    public char slowestKey(int[] releaseTimes, String keysPressed) {
        char ans = keysPressed.charAt(0);
        int mx = releaseTimes[0];
        for (int i = 1; i < releaseTimes.length; ++i) {
            int d = releaseTimes[i] - releaseTimes[i - 1];
            if (d > mx || (d == mx && keysPressed.charAt(i) > ans)) {
                mx = d;
                ans = keysPressed.charAt(i);
            }
        }
        return ans;
    }
}

// Accepted solution for LeetCode #1629: Slowest Key
func slowestKey(releaseTimes []int, keysPressed string) byte {
	ans := keysPressed[0]
	mx := releaseTimes[0]
	for i := 1; i < len(releaseTimes); i++ {
		d := releaseTimes[i] - releaseTimes[i-1]
		if d > mx || (d == mx && keysPressed[i] > ans) {
			mx = d
			ans = keysPressed[i]
		}
	}
	return ans
}

# Accepted solution for LeetCode #1629: Slowest Key
class Solution:
    def slowestKey(self, releaseTimes: List[int], keysPressed: str) -> str:
        ans = keysPressed[0]
        mx = releaseTimes[0]
        for i in range(1, len(keysPressed)):
            d = releaseTimes[i] - releaseTimes[i - 1]
            if d > mx or (d == mx and ord(keysPressed[i]) > ord(ans)):
                mx = d
                ans = keysPressed[i]
        return ans

// Accepted solution for LeetCode #1629: Slowest Key
struct Solution;

impl Solution {
    fn slowest_key(release_times: Vec<i32>, keys_pressed: String) -> char {
        let mut res = (0, ' ');
        let mut prev = 0;
        for (i, c) in keys_pressed.char_indices() {
            res = res.max((release_times[i] - prev, c));
            prev = release_times[i];
        }
        res.1
    }
}

#[test]
fn test() {
    let release_times = vec![9, 29, 49, 50];
    let keys_pressed = "cbcd".to_string();
    let res = 'c';
    assert_eq!(Solution::slowest_key(release_times, keys_pressed), res);
    let release_times = vec![12, 23, 36, 46, 62];
    let keys_pressed = "spuda".to_string();
    let res = 'a';
    assert_eq!(Solution::slowest_key(release_times, keys_pressed), res);
}

// Accepted solution for LeetCode #1629: Slowest Key
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #1629: Slowest Key
// class Solution {
//     public char slowestKey(int[] releaseTimes, String keysPressed) {
//         char ans = keysPressed.charAt(0);
//         int mx = releaseTimes[0];
//         for (int i = 1; i < releaseTimes.length; ++i) {
//             int d = releaseTimes[i] - releaseTimes[i - 1];
//             if (d > mx || (d == mx && keysPressed.charAt(i) > ans)) {
//                 mx = d;
//                 ans = keysPressed.charAt(i);
//             }
//         }
//         return ans;
//     }
// }

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n)

Space

O(1)

Approach Breakdown

BRUTE FORCE

O(n²) time

O(1) space

Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.

OPTIMIZED

O(n) time

O(1) space

Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.

Shortcut: If you are using nested loops on an array, there is almost always an O(n) solution. Look for the right auxiliary state.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.