# Slowest Key
**Difficulty:** EASY
[External](https://leetcode.com/problems/slowest-key)
Canonical: https://scaleengineer.com/dsa/problems/slowest-key
**Data structures:** Array, String
---
## Problem
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._

**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] <= 109`
* `releaseTimes[i] < releaseTimes[i+1]`
* `keysPressed` contains only lowercase English letters.

# Approaches
## Sorting Approach
This approach involves calculating the duration for each keypress and storing it along with the corresponding key. After collecting all keypress data, we sort this data to find the key with the longest duration, handling ties by choosing the lexicographically largest key.
**Time:** O(N log N), where N is the number of keypresses. The dominant operation is sorting the list of N keypresses. · **Space:** O(N), as we use an auxiliary list to store the data for all N keypresses.
**Pros:** Conceptually straightforward, separating the data collection from the processing.; Easy to understand and implement if familiar with sorting and custom comparators.
**Cons:** Less efficient in terms of both time and space compared to a single-pass solution.; Requires extra memory proportional to the input size.
### Explanation
This approach works by first calculating all keypress durations and then sorting them to find the desired key.

*   **Data Collection**: We iterate through the input arrays. For the first key, the duration is `releaseTimes[0]`. For any subsequent key at index `i`, the duration is `releaseTimes[i] - releaseTimes[i-1]`. We store each `(duration, key)` pair in a list. A custom class or a simple pair object can be used for this.
*   **Sorting**: Once we have the list of all keypresses, we sort it. The sorting logic is crucial:
    1.  Primary sort key: duration, in descending order.
    2.  Secondary sort key (for ties): the character, in descending lexicographical order.
*   **Result**: After sorting, the first element in the list will correspond to the keypress with the longest duration (and the lexicographically largest key in case of a tie). We return the key of this element.

Here is a Java implementation demonstrating this approach:
```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    // A helper class to store keypress information
    class KeyPress {
        int duration;
        char key;

        KeyPress(int duration, char key) {
            this.duration = duration;
            this.key = key;
        }
    }

    public char slowestKey(int[] releaseTimes, String keysPressed) {
        List<KeyPress> keyPresses = new ArrayList<>();
        
        // Handle the first keypress
        keyPresses.add(new KeyPress(releaseTimes[0], keysPressed.charAt(0)));

        // Handle subsequent keypresses
        for (int i = 1; i < releaseTimes.length; i++) {
            int duration = releaseTimes[i] - releaseTimes[i - 1];
            keyPresses.add(new KeyPress(duration, keysPressed.charAt(i)));
        }

        // Sort the list based on duration (desc) and then key (desc)
        Collections.sort(keyPresses, (a, b) -> {
            if (a.duration != b.duration) {
                return b.duration - a.duration; // Descending by duration
            } else {
                return b.key - a.key; // Descending by key (lexicographically)
            }
        });

        // The first element after sorting is the answer
        return keyPresses.get(0).key;
    }
}
```
### Algorithm
- Create a list of objects or pairs, say `keypresses`, to store `(duration, key)`.
- Calculate the duration for the first key: `d0 = releaseTimes[0]`. Add `(d0, keysPressed.charAt(0))` to `keypresses`.
- Loop from `i = 1` to `n-1`:
    - Calculate duration: `di = releaseTimes[i] - releaseTimes[i-1]`.
    - Add `(di, keysPressed.charAt(i))` to `keypresses`.
- Sort the `keypresses` list. The custom comparator should first compare durations in descending order. If durations are equal, it should compare keys in descending lexicographical order.
- Return the key from the first element of the sorted list.

## Single-Pass Iteration
This is the most efficient approach. We can determine the slowest key by iterating through the keypresses just once. We maintain two variables: one for the maximum duration found so far and one for the corresponding key. As we iterate, we update these variables whenever we find a keypress with a longer duration or a keypress with the same duration but a lexicographically larger key.
**Time:** O(N), where N is the number of keypresses. We iterate through the input arrays only once. · **Space:** O(1), as we only use a constant amount of extra space for variables, regardless of the input size.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).; Efficient and concise.
**Cons:** Combines logic for finding the max and handling ties within a single loop, which might be slightly less readable for a beginner compared to separating the concerns.
### Explanation
This optimal approach finds the slowest key in a single pass through the input arrays, using constant extra space.

*   **Initialization**: We start by assuming the first keypress is the slowest. We initialize a variable `maxDuration` with the duration of the first keypress (`releaseTimes[0]`) and a variable `slowestKey` with the first key itself (`keysPressed.charAt(0)`).
*   **Iteration**: We then loop through the rest of the keypresses, from the second one (`i = 1`) to the end.
*   **Comparison and Update**: In each step of the loop, we calculate the `currentDuration` (`releaseTimes[i] - releaseTimes[i-1]`) and compare it with our tracked `maxDuration`.
    *   If `currentDuration` is strictly greater than `maxDuration`, we have found a new slowest key. We update `maxDuration` to `currentDuration` and `slowestKey` to the current key (`keysPressed.charAt(i)`).
    *   If `currentDuration` is equal to `maxDuration`, we must check the tie-breaking rule. We compare the current key with the current `slowestKey`. If the current key is lexicographically larger, we update `slowestKey` to the current key.
*   **Result**: After the loop finishes, the `slowestKey` variable will hold the final answer.

Here is the Java code for the single-pass approach:
```java
class Solution {
    public char slowestKey(int[] releaseTimes, String keysPressed) {
        int n = releaseTimes.length;
        int maxDuration = releaseTimes[0];
        char slowestKey = keysPressed.charAt(0);

        for (int i = 1; i < n; i++) {
            int currentDuration = releaseTimes[i] - releaseTimes[i - 1];
            char currentKey = keysPressed.charAt(i);
            
            // Check for a new max duration or a tie with a lexicographically larger key
            if (currentDuration > maxDuration) {
                maxDuration = currentDuration;
                slowestKey = currentKey;
            } else if (currentDuration == maxDuration) {
                if (currentKey > slowestKey) {
                    slowestKey = currentKey;
                }
            }
        }
        
        return slowestKey;
    }
}
```
### Algorithm
- Initialize `maxDuration = releaseTimes[0]`.
- Initialize `slowestKey = keysPressed.charAt(0)`.
- Loop from `i = 1` to `n-1`:
    - Calculate `currentDuration = releaseTimes[i] - releaseTimes[i-1]`.
    - If `currentDuration > maxDuration`:
        - Set `maxDuration = currentDuration`.
        - Set `slowestKey = keysPressed.charAt(i)`.
    - Else if `currentDuration == maxDuration`:
        - If `keysPressed.charAt(i) > slowestKey`:
            - Set `slowestKey = keysPressed.charAt(i)`.
- Return `slowestKey`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  char slowestKey(vector<int> &releaseTimes, string keysPressed) {
    char ans = keysPressed[0];
    int mx = releaseTimes[0];
    for (int i = 1, n = releaseTimes.size(); i < n; ++i) {
      int d = releaseTimes[i] - releaseTimes[i - 1];
      if (d > mx || (d == mx && keysPressed[i] > ans)) {
        mx = d;
        ans = keysPressed[i];
      }
    }
    return ans;
  }
};

```

### Python

```python
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

```