[LeetCode 75] 933. Number of Recent Calls

Solution)

class RecentCounter:
    def __init__(self):
        # This deque will save requests that are called in ping()
        self.requests = collections.deque()

    def ping(self, t: int) -> int:
        # First append the input t
        self.requests.append(t)

        # This while loop will pop requests that are not in the range
        # of the past 3000 milliseconds
        while not (t-3000 <= self.requests[0] <= t):
            self.requests.popleft()
        
        # Once all the elements in requests are in the range of the
        # past 3000 milliseconds, we'll return the length of requests.
        # Length of requests indicates the number of valid requests in the range.
        return len(self.requests)

 
Problem: LeetCode
 
Time Complexity: O(n)
Space Complexity: O(n)
 

Explanation)

We'll use deque(doubly-ended-queue) to represent a queue.
 
This queue will save the times t, time when requests are made in the method ping().
 
When ping() is called, we'll check if the elements in the front indexes are in the valid range of (t-3000, t).
Once all the elements are in the range, we'll return the length of the queue.
 

1. Initialization)

When the class RecentCounter, we need some kind of memory to store past request times.
A list or a queue will do that job. (We cannot exploit a hashmap because we need to store them in order)
 
It's better to use queue because we can easily access the 0th element using its FIFO property.
 

class RecentCounter:
    # 1. Initialization
    def __init__(self):
        self.requests = collections.deque()

 

2. Ping)

Before checking if all the elements are in the range, we'll append the input t to requests.
Having t as an element in requests, this allows us to make sure that there is at least one element that is in the range.
 
After appending the new request time t, we'll check if all the elements are in the range. Since we're guaranteed that the input t's are in order, we'll start looking from the 0th element.
 
Run a while loop that checks if the 0th element is in the range. If it's not in the range, we'll pop it and keep checking until the 0th element is in the range.
 
Once requests only has elements that are in range, we'll return its length. The length of deque indicates the number of requests that were called in the range.
 

class RecentCounter:
    # 1. Initialization
    def __init__(self):
        self.requests = collections.deque()

    # 2. ping()
    def ping(self, t: int) -> int:
        self.requests.append(t)

        while not (t-3000 <= self.requests[0] <= t):
            self.requests.popleft()
        
        return len(self.requests)

---

 
 
It's been a while! I've been focusing on workouts recently. I DID NOT want to be stuck on graph problems again, so I chose to work on easy problems first. I might have been procrastinating for a while, but it feels great to be back and solving problems :)