JavaScript solution & detailed walkthrough of solving process


  • 0
    P

    I've written up my step-by-step solve of this problem, as well as rationale and thinking process. I solved this problem "offline" to simulate an interview-like environment. Any comments welcome!

    Initial Analysis

    It's trivial to get max in a window, which is an array of integers (from here on, k = # of integers int he window). However, you can't do better than O(k) when finding the max in an array of k integers.

    The difficulty of this problem is figuring out a more efficient way than O(n * k) - because you're finding the max of k integers, n times. We need to find a data structure that efficiently does these three operations:

    • RemoveOldest - remove the oldest inserted integer
    • Add - new integer
    • ComputeMax - amongst all integers in data structure

    Using a simple array, the costs are:

    • RemoveOldest: O(1)
    • Add: O(1)
    • ComputeMax: O(k)

    Now we hunt for something that does compute max better than O(k)

    Data Structures - Priority Queue

    When thinking about problems dealing with maximum numbers, my first thought usually goes to Priority Queues, which gives us O(logn) inserts and removals and gives us the current max for free. But this doesn't really work here - as we move the window, we're not removing the max number, but instead we need to remove the oldest number in the window. We'll have to search through the entire queue and remove it, which costs k.

    • RemoveOldest: O(k)
    • Add: O(logk)
    • ComputeMax: O(1)

    Sorting

    Another line of thought, since we need an efficient ComputeMax, is to sort the numbers in the window. The challenge here is to have a reasonable RemoveOldest and Add. I think this is a pretty deep rabbit hole, since you can come up with a number of convoluted data structures which will be hard to implement in the time of an interview. One example would be:

    BST (binary search trees) gives us O(logk) for all the operations we need. The tricky thing is we'll need to keep the BST in sync with the window. Say k = 4 for the window:

    [0, 5, 2, -1], 3, 3
    

    Our tree would be

        0
      /   \
     -1    5
          /
         2
    

    Moving the window to the right, we'll have

    0, [5, 2, -1, 3], 3
    

    We'll need to remove 0 and add 3.

        2
      /   \
     -1    5
          /
         3
    

    The max will always be the right most node (5 in both these windows), and we can compute that in O(logk) - assuming the tree is balanced.

    The catch here is we'll have to also keep track of which number to remove from the BST and account for duplicate numbers. In an interview, at this point I'd present this solution but also keep searching for something cleaner and more efficient.

    Digging Deeper

    Since we can't find an off-the-shelf data structure to "hole-in-one" this problem, we'll have to dig in a little more. The nice thing about this problem is we can safely assume we're going to be iterating through the array one way or another, so let's play out a few iterations.

    [0, 5, 2], -1, 3, 3
    // ComputeMax (0, 5, 2): 5
    
    0, [5, 2, -1], 3, 3
    // Remove 0
    // ComputeMax (5, 2, -1): 5
    
    0, 5, [2, -1, 3], 3
    // Remove 5
    // ComputeMax (2, -1, 3): 3
    

    Here we make a crucial observation. Certain numbers can never be a maximum, because they're surrounded by bigger numbers. For example, for -1 above, we know it doesn't need to be considered, because the windows it's in are [5, 2, -1], [2, -1, 3] and [-1, 3, 3]. When do we know for sure that -1 doesn't need to be considered and what's the rule?

    -1 won't be a max because it's followed by a larger value, 3. By the time we spot 3, we know -1 will never be a consideration. What happens if we keep a running tally of possible candidates?

    0, 5, 2, -1, 3, 3
    ^
    # [0]
    
    0, 5, 2, -1, 3, 3 
       ^
    # [5], we can discard 0 since 5 > 0
    
    
    0, 5, 2, -1, 3, 3 
          ^
    # [5, 2]
    
    0, 5, 2, -1, 3, 3 
              ^
    # [5, 2, -1]
    
    0, 5, 2, -1, 3, 3 
                 ^
    # [5, 3] we discard 2 and -1 since 3 is greater than both of them 
    
    0, 5, 2, -1, 3, 3 
                    ^
    # [5, 3, 3] we discard 2 and -1 since 3 is greater than both of them
    

    If we take the first element of the possible max candidates, it looks pretty close to the result; except when the window moves past -1 and we're still stuck with 5 as our max. What we need to do is ensure our candidates array keeps within the window.

    A straightforward way to do this is keep two values in the array, one for the index and the other the value.

    i = 0
    0, 5, 2, -1, 3, 3
    ^
    # [{ index: 0, v: 0 }]
    
    i = 1
    0, 5, 2, -1, 3, 3 
       ^
    # [{ index: 1, v: 5 }]
    
    i = 2
    0, 5, 2, -1, 3, 3 
          ^
    # [{ index: 1, v: 5 }, { index: 2, v: 2 }]
    
    i = 3
    0, 5, 2, -1, 3, 3 
              ^
    # [{ index: 1, v: 5 }, { index: 2, v: 2 }, { index: 3, v: -1}]
    
    i = 4
    0, 5, 2, -1, 3, 3 
                 ^
    # [{ index: 1, v: 5 }, { index: 4, v: 3 }]
    

    A cleaner way would be to store only the indexes, and lookup the corresponding value from our input array, since that lookup is O(1).

    Our window size is k = 3. Since the window contains the current element, we'll be looking back 3 - 1 = 2 elements, i.e. if the current index is 4, the furthest we'll look back is i - (k - 1) = i - k + 1 = 2. Any indexes less than that need to be discarded. Accordingly, we drop 5 as a potential max.

    In pseudo code, our algorithm would be:

    given input and k
    
    let candidates = new Deque()
    let windowMax = []
    
    for num, i in input
       # make sure candidates is in window
       while candidates.first() < i - k + 1
         candidates.removeFirst()
       
       # remove candidates smaller than the current item
       while candidates.last() < input[i]
         candidates.removeLast()
    
       candidates.addLast(input[i])
       
      # need at least k items to calculate a window 
       if (i + 1 >= k) windowMax.add(candidates[0])
    
    return windowMax
    

    We need at least k items to calculate a window. At each i we have i + 1 items, so we add to windowMax if i + 1 >= k

    Note that candidates is a Deque, which is a double-ended queue. This means we can remove and add items to either the front or back of the list in O(1). Basically a doubly-linked list.

    Complexity

    Looking at our original requirements, the way we're using a Deque gives us the following:

    • RemoveOldest O(1)
    • Add O(1)
    • ComputeMax O(1)* (first element)

    Now I put a * next to the O(1) compute max, since it's only "free" because of our additional logic. The good news is that additional logic is bounded by n, since we insert/remove each element of the input at most once. So overall, this solution is O(n).

    Full solution for JavaScript below.

    
    var maxSlidingWindow = function(nums, k) {
        var candidates = new Deque()
        var windowMax = []
    
        for (var i = 0; i < nums.length; i++) {
           //  make sure candidates is in window
           while (candidates.first() && candidates.first().val < i - k + 1) {
             candidates.removeFirst()
           }
           
           // remove candidates smaller than the current item
           while (candidates.last() && nums[candidates.last().val] < nums[i]) {
             candidates.removeLast()
           }
        
           candidates.addLast(i)
           
          // need at least k items to calculate a window
          if (i + 1 >= k) windowMax.push(nums[candidates.first().val])
        }
        
        return windowMax
    }
    
    // Data Structures
    function LinkItem(val) {
        this.val = val
    }
    
    function Deque() {
        var _first = null
        var _last = null
        
        this.first = function() {
            return _first
        }
        
        this.last = function() {
            return _last
        }
        
        this.addLast = function(val) {
            if (!_first) {
                _first = new LinkItem(val)
                _last = _first
            } else {
                var newItem = new LinkItem(val)
                _last.next = newItem
                newItem.prev = _last
                
                _last = newItem
            }
        }
        
        this.removeFirst = function() {
            if (!_first) return
            
            _first = _first.next
            if (!_first) {
                _last = null
            } else {
                _first.prev = null
            }
        }
        
        this.removeLast = function() {
            if (!_last) return
            
            _last = _last.prev
            if (!_last) {
                _first = null
            } else {
                _last.next = null
            }
        }
    }
    

Log in to reply
 

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