Problem of The Day: Slowest Key

4 min read 852 words

Problem Statement

leetcode problem link

Solution [accepted]

class Solution:
    def slowestKey(self, releaseTimes: List[int], keysPressed: str) -> str:
        res = keysPressed[0]
        longest = releaseTimes[0]
        n = len(keysPressed)
        for i in range(1, n):
            time = releaseTimes[i] - releaseTimes[i - 1]
            if longest < time:
                longest = time
                res = keysPressed[i]
            if longest == time:
                if ord(res) < ord(keysPressed[i]):
                    res = keysPressed[i]

        return res

public class Solution {
    public char SlowestKey(int[] releaseTimes, string keysPressed) {
        int n = releaseTimes.Length;
        char res = keysPressed[0];
        int longest = releaseTimes[0];
        for (int i = 1; i < n; i++) {
            int time = releaseTimes[i] - releaseTimes[i - 1];
            if (longest < time || (longest == time && keysPressed[i] >= res)) {
                longest = time;
                res = keysPressed[i];
            }
        }

        return res;
    }
}

• time: O(n)
• space: O(1)

Editorial

Approach 1: Using Map

class Solution {
public:
    char slowestKey(vector<int>& releaseTimes, string keysPressed) {
        unordered_map<char, int> durationMap;
        durationMap[keysPressed[0]] = releaseTimes[0];
        // find and store the keypress duration for each key in the durationMap
        for (int i = 1; i < releaseTimes.size(); i++) {
            int currentDuration = releaseTimes[i] - releaseTimes[i - 1];
            char currentKey = keysPressed[i];
            durationMap[currentKey] =
                max(durationMap[currentKey], currentDuration);
        }
        char slowestKey = ' ';
        int longestPressDuration = 0;
        // iterate over the map to find the slowest key
        for (auto mapElement : durationMap) {
            char key = static_cast<char>(mapElement.first);
            int duration = static_cast<int>(mapElement.second);
            if (duration > longestPressDuration) {
                longestPressDuration = duration;
                slowestKey = key;
            } else if (duration == longestPressDuration && key > slowestKey) {
                slowestKey = key;
            }
        }
        return slowestKey;
    }
};

Approach 3: Constant Extra Space

class Solution {
public:
    char slowestKey(vector<int>& releaseTimes, string keysPressed) {
        int n = releaseTimes.size();
        int longestPress = releaseTimes[0];
        char slowestKey = keysPressed[0];
        for (int i = 1; i < n; i++) {
            int currentDuration = releaseTimes[i] - releaseTimes[i - 1];
            // check if we found the key that is slower than slowestKey
            if (currentDuration > longestPress ||
                (currentDuration == longestPress &&
                 keysPressed[i] > slowestKey)) {
                // update the slowest key and longest press duration
                longestPress = currentDuration;
                slowestKey = keysPressed[i];
            }
        }
        return slowestKey;
    }
};