A problem worthy of attack, proves its worth by fighting back

These are the famous words by Paul Erdos:

“A problem worthy of attack, proves its worth by fighting back!” – Paul Erdos One of the greatest mathematicians of the 20th Century, Paul Erdos , is often associated with the following rhyme: “A problem worthy of attack, proves its worth by fighting back!”

I'm sure that he was thinking beyond a LeetCode problem :D But this one was worth an attack: https://leetcode.com/problems/alert-using-same-key-card-three-or-more-times-in-a-one-hour-period/

1604. Alert Using Same Key-Card Three or More Times in a One Hour Period

Medium

Leetcode company workers use key-cards to unlock office doors. Each time a worker uses their key-card, the security system saves the worker's name and the time when it was used. The system emits an alert if any worker uses the key-card three or more times in a one-hour period.

You are given a list of strings keyName and keyTime where [keyName[i], keyTime[i]] corresponds to a person's name and the time when their key-card was used in a single day.

Access times are given in the 24-hour time format "HH:MM", such as "23:51" and "09:49".

Return a list of unique worker names who received an alert for frequent keycard use. Sort the names in ascending order alphabetically.

Notice that "10:00" - "11:00" is considered to be within a one-hour period, while "23:51" - "00:10" is not considered to be within a one-hour period.

 

Example 1:

Input: keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"], keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"]
Output: ["daniel"]
Explanation: "daniel" used the keycard 3 times in a one-hour period ("10:00","10:40", "11:00").

Example 2:

Input: keyName = ["alice","alice","alice","bob","bob","bob","bob"], keyTime = ["12:01","12:00","18:00","21:00","21:20","21:30","23:00"]
Output: ["bob"]
Explanation: "bob" used the keycard 3 times in a one-hour period ("21:00","21:20", "21:30").

Example 3:

Input: keyName = ["john","john","john"], keyTime = ["23:58","23:59","00:01"]
Output: []

Example 4:

Input: keyName = ["leslie","leslie","leslie","clare","clare","clare","clare"], keyTime = ["13:00","13:20","14:00","18:00","18:51","19:30","19:49"]
Output: ["clare","leslie"]

 

Constraints:

• 1 <= keyName.length, keyTime.length <= 105
• keyName.length == keyTime.length
• keyTime are in the format "HH:MM".
• [keyName[i], keyTime[i]] is unique.
• 1 <= keyName[i].length <= 10
• keyName[i] contains only lowercase English letters.

We'll do one pass only. The approach was to keep a sorted list of times per name, but for the time you need to convert to decimal (easy: hour*60 + minute). But as you insert a new time, that's when you check whether the alert was triggered. Suppose that you added the new time at index INDEX. There are then 3 cases to check:

Val(INDEX + 2) - Val(INDEX)

Val(INDEX + 1) - Val(INDEX - 1)

Val(INDEX) - Val(INDEX - 2)

Once you do that, then it should work. I made several mistakes along the way, including using a SortedList first when all I needed was a Hashtable. Several attempts later, it worked. Code is below, cheers, ACC.

public class Solution
{
    public IList AlertNames(string[] keyName, string[] keyTime)
    {
        Hashtable nameToTimes = new Hashtable();

        List retVal = new List();
        Hashtable alreadyAdded = new Hashtable();
        for (int i = 0; i < keyName.Length; i++)
        {
            if (alreadyAdded.ContainsKey(keyName[i])) continue;

            int val = Convert24hToNumber(keyTime[i]);

            if (!nameToTimes.ContainsKey(keyName[i]))
            {
                SortedList times = new SortedList(val);
                times.Add(val, val);
                nameToTimes.Add(keyName[i], times);
            }
            else
            {
                SortedList times = (SortedList)nameToTimes[keyName[i]];
                times.Add(val, val);
                int index = times.IndexOfKey(val);

                //Check 2 before index first
                if (index - 2 >= 0 &&
                    (int)times.GetByIndex(index) - (int)times.GetByIndex(index - 2) > 0 &&
                    (int)times.GetByIndex(index) - (int)times.GetByIndex(index - 2) <= 60 &&
                    !alreadyAdded.ContainsKey(keyName[i]))
                {
                    alreadyAdded.Add(keyName[i], true);
                    retVal.Add(keyName[i]);
                }

                //Check 2 after index next
                if (index + 2 < times.Count &&
                    (int)times.GetByIndex(index + 2) - (int)times.GetByIndex(index) > 0 &&
                    (int)times.GetByIndex(index + 2) - (int)times.GetByIndex(index) <= 60 &&
                    !alreadyAdded.ContainsKey(keyName[i]))
                {
                    alreadyAdded.Add(keyName[i], true);
                    retVal.Add(keyName[i]);
                }

                //Check the one next to each
                if (index + 1 < times.Count && 
                    index - 1 >= 0 &&
                    (int)times.GetByIndex(index + 1) - (int)times.GetByIndex(index - 1) > 0 &&
                    (int)times.GetByIndex(index + 1) - (int)times.GetByIndex(index - 1) <= 60 &&
                    !alreadyAdded.ContainsKey(keyName[i]))
                {
                    alreadyAdded.Add(keyName[i], true);
                    retVal.Add(keyName[i]);
                }
            }
        }

        retVal.Sort();

        return retVal;
    }

    private int Convert24hToNumber(string time)
    {
        string[] parts = time.Split(':');

        int hours = Int32.Parse(parts[0]);
        int minutes = Int32.Parse(parts[1]);

        int retVal = hours * 60 + minutes;
        return retVal;
    }
}