Java - sliding window approach, O(1) for both space and each method call


  • 0
    A

    Use a linked list as a window to keep hit frequency and shrink its size to trim any time stamp that is more than 300. Each node store the total frequency of the same time stamp.

    One more thing, to avoid overflow, the type of lower and upper boundary could be long instead of int. Thanks for reading.

    public class HitCounter 
    {
        int winLo = 0, winHi = 0; 
        LinkedList<int[]> win = new LinkedList<int[]>();
    
        public HitCounter() {
        }
        
        public void hit(int timestamp) 
        {
            winHi++;
            
            if(win.size() == 0 || win.getLast()[0] != timestamp)
                win.add(new int[] { timestamp, winHi});
            else
                win.getLast()[1] = winHi;
                
            ShrinkWin(timestamp);
        }
        
        public int getHits(int timestamp) 
        {
            ShrinkWin(timestamp);
            return (int)(winHi - winLo);
        }
        
        private void ShrinkWin(int timestamp)
        {
            while (win.size() > 0 && timestamp - win.getFirst()[0] >= 300) 
            {
                winLo = win.getFirst()[1];
                win.removeFirst();
            }        
        }
    }

Log in to reply
 

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