MediumNo. 1604
Alert Using Same Key-Card Three or More Times in a One Hour Period — LeetCode 1604 Python Solution
- Pattern
- Sorting
- Topics
- Array, Hash Table, String, Sorting
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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.
Example
- 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").
Python solution
class Solution:
def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
d = defaultdict(list)
for name, t in zip(keyName, keyTime):
t = int(t[:2]) * 60 + int(t[3:])
d[name].append(t)
ans = []
for name, ts in d.items():
if (n := len(ts)) > 2:
ts.sort()
for i in range(n - 2):
if ts[i + 2] - ts[i] <= 60:
ans.append(name)
break
ans.sort()
return ansComplexity
- Time
- O(n × log n)
- Space · auxiliary
- O(n)
Pattern: Sorting
Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 1604. Alert Using Same Key-Card Three or More Times in a One Hour Period is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.
The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0049 | Group Anagrams | Medium |
| 0522 | Longest Uncommon Subsequence II | Medium |
| 0692 | Top K Frequent Words | Medium |
| 0720 | Longest Word in Dictionary | Medium |
| 0721 | Accounts Merge | Medium |
| 0792 | Number of Matching Subsequences | Medium |
Frequently asked questions
- How hard is LeetCode 1604. Alert Using Same Key-Card Three or More Times in a One Hour Period?
LeetCode 1604. Alert Using Same Key-Card Three or More Times in a One Hour Period is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1604. Alert Using Same Key-Card Three or More Times in a One Hour Period?
The Python solution on this page runs in O(n × log n).
- What is the space complexity of LeetCode 1604. Alert Using Same Key-Card Three or More Times in a One Hour Period?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1604. Alert Using Same Key-Card Three or More Times in a One Hour Period cover?
LeetCode 1604. Alert Using Same Key-Card Three or More Times in a One Hour Period is tagged Array, Hash Table, String and Sorting on LeetCode.