My easy Java Solution, beating 88%


  • 0

    The idea is quite simple and similar to existing solutions, while I find it faster if we do the removal in getHit(), instead of doing it in both hit() and getHit().

    public class HitCounter {
        List<Integer> hitList = new ArrayList<Integer>();
        /** Initialize your data structure here. */
        public HitCounter() {
        }
        
        /** Record a hit.
            @param timestamp - The current timestamp (in seconds granularity). */
        public void hit(int timestamp) {
            hitList.add(timestamp);
        }
        
        /** Return the number of hits in the past 5 minutes.
            @param timestamp - The current timestamp (in seconds granularity). */
        public int getHits(int timestamp) {
            while(hitList.size()>0 && (timestamp - hitList.get(0))>=300)
                hitList.remove((int)0);
            return hitList.size();
        }
    }
    

  • 1
    U

    @YuTingLiu It's not a memory efficient solution. Suppose there is no call to getHits for 6 months then can you imagine size of hitList? So IMO, the part of removing elements from hList should be done in hit method instead of getHits method. As maximum size of hitList is 300 so hit method would still cost O(1).


  • 0

    @ufarooqi You are right. It is better to use a fixed size of bucket to store the log like the top voted posts. Thanks for letting me know that!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.