1629. Slowest Key

EasyArrayString

Problem Description

In this problem, we are simulating the operation of a keypad being tested. The tester pressed keys in sequence, and we're given two pieces of information: the sequence of keys that were pressed and the times when each key was released.

The sequence of keys is represented by a string called keysPressed, where each character corresponds to a key that was pressed. The release times are given in an array releaseTimes, which includes the time when each key was released. Note that the array is sorted; the keys have been pressed in the order given by the string keysPressed, starting at time 0.

The duration of a keypress is defined as the time difference between the release of the current key and the release of the previous key. For the first key (index 0), its duration is simply its release time.

The aim is to find the key that had the longest keypress duration. If there are several keys with the same longest duration, we need to return the key with the highest lexicographical order (the one that appears last in the alphabet).

Intuition

To find the solution, we iterate through the keysPressed string and releaseTimes array to calculate the durations of all keypresses. To do this, we subtract the release time of the previous key from the release time of the current key.

We maintain two variables, mx for the maximum duration we have encountered so far and ans for the key that corresponds to this maximum duration. As we loop through the keys:

If we find a keypress duration longer than the current maximum duration (mx), we update both mx and ans with the new values.
If we find a keypress duration equal to the maximum duration (mx), we compare the current key with the key in ans lexicographically, and if the current key is lexicographically larger (i.e., it comes later in the alphabet), we update ans.

The logic above ensures that we will end with the key that has the longest duration, and if there is a tie, we will have the key with the highest lexicographical order.

Solution Approach

The solution uses a straightforward iteration and comparison approach without the need for complex data structures or algorithms. The variables mx and ans hold the information of the maximum duration encountered and the corresponding key respectively.

Here is a step-by-step breakdown:

Initialize mx with the release time of the first key, as there is no previous key to calculate the duration with, so the duration is releaseTimes[0].
Initialize ans with the first key itself from the keysPressed string.
Loop through indices from 1 to len(keysPressed) - 1 (since we have already used the 0th index for initialization).
- Calculate the duration d for the ith keypress as releaseTimes[i] - releaseTimes[i - 1].
- Compare this duration with the current maximum duration mx.
- If the current duration d is greater than mx, update both mx and ans with the current duration and key.
- If the current duration d is equal to mx, compare the keys lexicographically.
  - We compare keys by their ASCII values using ord(). If the ASCII value of the current key keysPressed[i] is greater than that of ans (which means it is lexicographically larger), then update ans with the current key.
Continue this process until the loop finishes.
Return ans, which contains the key of the longest keypress duration or the lexicographically largest key if there are ties.

By using this direct method, we ensure a time complexity of O(n), where n is the length of the keysPressed, which is optimal since we have to examine each keypress to find the answer.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate the solution approach.

Consider the input where keysPressed is "cbcd" and releaseTimes is [1, 2, 4, 7].

Following the step-by-step solution approach:

Initialize mx with the release time of the first key, which is releaseTimes[0] = 1. There is no previous key, so the duration for this keypress is just its release time.
Initialize ans with the first key from the keysPressed string, which is "c".
Now, we will loop through the indices from 1 to len(keysPressed) - 1, which in this case is from 1 to 3.
- For index 1:
  - Calculate the duration d as releaseTimes[1] - releaseTimes[0], which is 2 - 1 = 1.
  - Compare d to mx. Here, d is equal to mx, which is 1.
  - Since d is equal to mx, we compare keysPressed[1] with ans lexicographically. Here, "b" is less than "c", so we don't update ans.
- For index 2:
  - Calculate d as releaseTimes[2] - releaseTimes[1], which equals 4 - 2 = 2.
  - Now d is greater than mx (2 > 1), so we update mx to 2 and ans to keysPressed[2] which is "c".
- For index 3:
  - Calculate d as releaseTimes[3] - releaseTimes[2], which equals 7 - 4 = 3.
  - Again, d is greater than mx (3 > 2), so we update mx to 3 and ans to keysPressed[3] which is "d".
After completing the loop, the maximum duration mx is 3 and the corresponding key ans is "d".
We return ans, which is "d". This is the key with the longest keypress duration. If there had been any ties, the solution would have returned the key with the highest lexicographical order.

There you have the walkthrough using the provided solution approach on a straightforward example. This shows how we can find the key with the longest duration or the lexicographically largest one in case of ties.

Solution Implementation

1from typing import List
2
3class Solution:
4    def slowestKey(self, release_times: List[int], keys_pressed: str) -> str:
5        # Initialize the slowest key with the first key pressed
6        slowest_key = keys_pressed[0]
7        # Initialize the maximum duration with the duration of the first key
8        max_duration = release_times[0]
9      
10        # Iterate over the keys pressed except the first one
11        for i in range(1, len(keys_pressed)):
12            # Calculate the duration of the current key pressed
13            duration = release_times[i] - release_times[i - 1]
14          
15            # If current duration is greater than max_duration
16            # or it's equal but the key is lexicographically greater,
17            # update slowest_key and max_duration
18            if duration > max_duration or (duration == max_duration and 
19                                           ord(keys_pressed[i]) > ord(slowest_key)):
20                max_duration = duration
21                slowest_key = keys_pressed[i]
22      
23        # Return the slowest key after iterating all keys
24        return slowest_key
25

1class Solution {
2    public char slowestKey(int[] releaseTimes, String keysPressed) {
3        // Initialize the slowest key to the first key pressed
4        char slowestKey = keysPressed.charAt(0);
5        // Initialize the maximum duration to the release time of the first key
6        int maxDuration = releaseTimes[0];
7      
8        // Iterate through the release times starting from the second element
9        for (int i = 1; i < releaseTimes.length; ++i) {
10            // Calculate the duration the key was held down
11            int duration = releaseTimes[i] - releaseTimes[i - 1];
12          
13            // Compare the current duration to the max duration
14            // Update if the current duration is greater, or if it's equal and the key is lexicographically larger
15            if (duration > maxDuration || (duration == maxDuration && keysPressed.charAt(i) > slowestKey)) {
16                maxDuration = duration; // Update the max duration
17                slowestKey = keysPressed.charAt(i); // Update the slowest key
18            }
19        }
20      
21        // Return the slowest key with the longest duration
22        return slowestKey;
23    }
24}
25

1#include <vector>
2#include <string>
3
4class Solution {
5public:
6    // Function to determine the slowest key
7    char slowestKey(vector<int>& releaseTimes, string keysPressed) {
8        // Initialize slowest key with the first key and set its duration
9        char slowestKeyChar = keysPressed[0];
10        int longestDuration = releaseTimes[0];
11      
12        // Loop through the rest of the keys
13        for (int i = 1; i < releaseTimes.size(); ++i) {
14            // Calculate the duration for each key press
15            int currentDuration = releaseTimes[i] - releaseTimes[i - 1];
16          
17            // Update the longest duration and slowest key if we find a longer duration
18            // or if the duration is equal and the key character is lexically greater
19            if (currentDuration > longestDuration || (currentDuration == longestDuration && keysPressed[i] > slowestKeyChar)) {
20                longestDuration = currentDuration;
21                slowestKeyChar = keysPressed[i];
22            }
23        }
24        // Return the slowest key character found
25        return slowestKeyChar;
26    }
27};
28

1// Function to determine the slowest key
2function slowestKey(releaseTimes: number[], keysPressed: string): string {
3    // Initialize slowest key with the first key and set its duration
4    let slowestKeyChar: string = keysPressed[0];
5    let longestDuration: number = releaseTimes[0];
6  
7    // Loop through the rest of the key release times
8    for (let i = 1; i < releaseTimes.length; i++) {
9        // Calculate the duration for each key press
10        const currentDuration: number = releaseTimes[i] - releaseTimes[i - 1];
11      
12        // Update the longest duration and slowest key if we find a longer duration,
13        // or if the duration is equal and the key character is lexically greater
14        if (currentDuration > longestDuration || 
15           (currentDuration === longestDuration && keysPressed[i] > slowestKeyChar)) {
16            longestDuration = currentDuration;
17            slowestKeyChar = keysPressed[i];
18        }
19    }
20
21    // Return the slowest key character found
22    return slowestKeyChar;
23}
24

Time and Space Complexity

The provided Python code defines a function slowestKey that determines the character in keysPressed that has the longest duration between key presses. The code iterates through the keysPressed string and uses the releaseTimes list to find that character. Here's a breakdown of the time complexity and space complexity:

Time Complexity: The time complexity of the function is O(n), where n is the length of the keysPressed string (and also the length of the releaseTimes list). This is because the code iterates through the keysPressed string exactly once.
Space Complexity: The space complexity of the function is O(1), which is constant space complexity. No additional space is used that scales with the input size. Only a fixed number of single-value variables are used (ans and mx), and their space usage does not depend on the size of the input.

The time complexity is derived from the single loop running through the input lists, and the space complexity is based on the fixed number of variables used in the function.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know