1629. Slowest Key

EasyArrayString
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following uses divide and conquer strategy?

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:

  1. 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].
  2. Initialize ans with the first key itself from the keysPressed string.
  3. 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.
  4. Continue this process until the loop finishes.
  5. 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.

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

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

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:

  1. 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.

  2. Initialize ans with the first key from the keysPressed string, which is "c".

  3. 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".

  4. After completing the loop, the maximum duration mx is 3 and the corresponding key ans is "d".

  5. 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
Not Sure What to Study? Take the 2-min Quiz：

How many times is a tree node visited in a depth first search?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the most two important steps in writing a depth first search function? (Select 2)

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫