DSAPROB25 - Editorial

editorial
, ,
1

Problem Link - Count Cricket Boundaries

Problem Statement:

You are tasked with implementing a BoundariesCounter class that counts the number of cricket boundaries (4s and 6s) within a certain time frame.

Approach:

The key idea is to use a queue to manage the timestamps of events. This allows us to efficiently keep track of events that happen within the last 10 minutes.

  1. Class Definition: We define a class BoundariesCounter that contains a queue to store event timestamps.

  2. Adding Events: The method getLast(int t) takes a timestamp t as input:

    • It adds the current timestamp t to the queue.
    • It then checks if any timestamps in the queue are older than t - 600 seconds (10 minutes). If they are, it removes them from the front of the queue.

  3. Counting Valid Events: After cleaning up old timestamps, the size of the queue tells us how many events have occurred in the last 10 minutes.

Time Complexity:

O(N) for processing all timestamps, where N is the number of events, as each event is added and potentially removed from the queue once.

Space Complexity:

O(N) for storing timestamps in the queue.