Slowest Key - Practice Coding Problems

Slowest Key - Problem

Array String Easy

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 are multiple such keypresses, return the lexicographically largest key of the keypresses.

Input & Output

Example 1 — Basic Case

$ Input: releaseTimes = [9,12,16,20], keysPressed = "abcd"

› Output: c

💡 Note: Durations: a=9, b=12-9=3, c=16-12=4, d=20-16=4. Maximum duration is 4. Both 'c' and 'd' have duration 4, but 'c' < 'd' lexicographically, so we return 'c'.

Example 2 — Lexicographical Tie

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

› Output: a

💡 Note: Durations: s=12, p=11, u=13, d=10, a=16. Maximum duration is 16 for key 'a'.

Example 3 — First Key Longest

$ Input: releaseTimes = [10,15,18], keysPressed = "xyz"

› Output: x

💡 Note: Durations: x=10, y=15-10=5, z=18-15=3. Maximum duration is 10 for key 'x'.

Constraints

1 ≤ releaseTimes.length ≤ 1000
0 < releaseTimes[i] ≤ 10⁹
releaseTimes[i-1] < releaseTimes[i] for all valid i
keysPressed.length == releaseTimes.length
keysPressed contains only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Release times and corresponding keys

Calculate Durations

Find time difference for each keypress

Find Maximum

Identify key with longest duration

Key Takeaway

🎯 Key Insight: Calculate key press duration as the difference between consecutive release times, then track the maximum duration with lexicographically largest key for ties

Asked in

a Amazon 15 Apple 8

The key insight is to calculate key press durations by subtracting consecutive release times, then find the key with maximum duration. For ties, choose the lexicographically largest key. The optimal approach processes in a single pass with O(n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass Optimal	O(n)	O(1)	Calculate duration and track maximum in one pass through the arrays
Brute Force - Calculate All Durations	O(n)	O(n)	Calculate duration for each keypress, then find the one with maximum duration

Single Pass Optimal — Algorithm Steps

Step 1: Initialize maxDuration = 0 and result with first key
Step 2: For each position, calculate current duration and update maximum if needed
Step 3: Handle ties by choosing lexicographically larger key

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with first key as result

Process Each Key

Calculate duration and update maximum

Handle Ties

Choose lexicographically larger key

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char solution(int* releaseTimes, int releaseTimesSize, char* keysPressed) {
    int maxDuration = releaseTimes[0];
    char result = keysPressed[0];
    
    // Process each keypress and track maximum
    for (int i = 1; i < releaseTimesSize; i++) {
        int duration = releaseTimes[i] - releaseTimes[i-1];
        
        if (duration > maxDuration || (duration == maxDuration && keysPressed[i] > result)) {
            maxDuration = duration;
            result = keysPressed[i];
        }
    }
    
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int releaseTimes[100];
    int size = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] >= '0' && token[0] <= '9') {
            releaseTimes[size++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    char keysPressed[100];
    fgets(keysPressed, sizeof(keysPressed), stdin);
    keysPressed[strcspn(keysPressed, "\n")] = 0;
    
    char result = solution(releaseTimes, size, keysPressed);
    printf("%c\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through both arrays to calculate durations and find maximum

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables to track maximum duration and result

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass Optimal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler