Optimize Leetcode 239. Sliding Window Maximum using Swift

Question

LeetCode problem 239. Sliding Window Maximum

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max  [1 3 -1] -3 5 3 6 7 3   1 [3 -1 -3] 5 3 6 7 3   1 3 [-1 -3 5] 3 6 7 5   1 3 -1 [-3 5 3] 6 7 5   1 3 -1 -3 [5 3 6] 7 6   1 3 -1 -3 5 [3 6 7] 7 

Constraints:

• 1 <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴
• 1 <= k <= nums.length

There is the brute force approach which runs at O(n*k) with 2 loops and surprisingly that got accepted on LeetCode when I was expecting a time out exception, however the run time faster than just 5% of the rest of the submissions.

After doing some research, I came across the deque (deck) approach which is said to be linear time and so I implemented a version using a swift array. The run time improved, however, it still said my submission was faster than only half of the other submissions which is fine, however, I expected this solution to do better since it improves from O(n*k) to O(n) and was suggested as one of the best solutions. Here are my results:

So my question is, can my code be improved / optimize further in terms of run time or is my assumption above wrong ?

func maxSlidingWindowDeque(_ nums: [Int], _ k: Int) -> [Int]
{
  if nums.count <= 1
  {
    return nums
  }
  
  var maxArray: [Int] = []
  var deque: [Int] = []
  
  for index in 0 ..< k
  {
    while !deque.isEmpty
    {
      if let lastIndex = deque.last,
         nums[index] > nums[lastIndex]
      {
        deque.removeLast()
        continue
      }
      
      break
    }
    
    deque.append(index)
  }
  
  for endIndex in k ..< nums.count
  {
    let currentMaxIndex = deque[0]
    
    maxArray.append(nums[currentMaxIndex])
    
    if !deque.isEmpty && deque[0] < (endIndex - k) + 1
    {
      deque.removeFirst()
    }
    
    while !deque.isEmpty
    {
      if let lastIndexInDeque = deque.last, nums[endIndex] >= nums[lastIndexInDeque]
      {
        deque.removeLast()
        continue
      }
      
      break
    }
    
    deque.append(endIndex)
  }
  
  if !deque.isEmpty
  {
    let maxValueIndex = deque[0]
    maxArray.append(nums[maxValueIndex])
  }
  
  return maxArray
}

Answer 1

I believe there might be better solutions out there so I am not marking this as the answer, however I saw an opportunity to make the code more succinct while the core logic as a whole is not too different.

For starters, I thought to remove the check of the array size being 0 or 1

if nums.count <= 1
{
    return nums
}

My thought process was that if indeed the array was this small, the following computations weren't really going to add any significant overhead.

The important thing to notice in this problem is that the first window is treated a bit differently as we do not have any numbers stored previously to compare against and we need to evaluate all k numbers in the window. In the initial solution, I divided these into 3 different parts.

// handling of the first window
for index in 0 ..< k
{
    while !deque.isEmpty
    {
      loops += 1
      print("Loops: \(loops)")
      
      if let lastIndex = deque.last,
         nums[index] > nums[lastIndex]
      {
        deque.removeLast()
        continue
      }
      
      break
    }
    
    deque.append(index)
}

// handling of all the subsequent windows
for endIndex in k ..< nums.count
  {
    let currentMaxIndex = deque[0]
    
    maxArray.append(nums[currentMaxIndex])
    
    if !deque.isEmpty && deque[0] < (endIndex - k) + 1
    {
      deque.removeFirst()
    }
    
    while !deque.isEmpty
    {
      loops += 1
      print("Loops: \(loops)")
      
      if let lastIndexInDeque = deque.last, nums[endIndex] >= nums[lastIndexInDeque]
      {
        deque.removeLast()
        continue
      }
      
      break
    }
    
    deque.append(endIndex)
}

// handling of the last max value
if !deque.isEmpty
{
    let maxValueIndex = deque[0]
    maxArray.append(nums[maxValueIndex])
}

While this works, I felt it would be nice to find a way to bring all this logic into one loop like below:

// Loop through the nums array
for currentIndex in 0 ..< nums.count
{
  // Same logic as before with the additional step below

  // Start building the max array only after we have
  // evaluated all 'k' numbers from the first window
  if currentIndex >= k - 1, !deque.isEmpty,
     let maxIndex = deque.first
  {
     // Append the max of the current window in he max array
     maxArray.append(nums[maxIndex])
  }
}

Although, these improvements are more on the code organization side than any major performance improvements. I checked both the versions to see if any version had some extra loops running which was not the case.

In conclusion, I ran both the code bases again on leet code at least 15 times and the original code in the question showed varying results from 3000+ miliseconds to under 2000ms, for example so I can say, there is no massive performance improvement as I initially thought but the takeaway was that maybe the numbers on LeetCode results should be taken with a grain of salt.

Finally, here is the updated version which is a bit more succinct and with some comments to explain the logic:

func maxSlidingWindowDeque(_ nums: [Int], _ k: Int) -> [Int]
{
  // Initialize a double ended queue to keep track of viable maximum numbers
  var deque: [Int] = []
  
  // An array that will be used to store the final max values to be returned
  var maxArray: [Int] = []
  
  // Loop through the nums array
  for currentIndex in 0 ..< nums.count
  {
    // If the deque is not empty, check if the first stored index is outside
    // the current window
    if !deque.isEmpty && deque[0] <= currentIndex - k
    {
      // Remove the first item in the deque as it is outside the current window
      deque.removeFirst()
    }
    
    // Loop through the current deque as long as it is not empty
    while !deque.isEmpty
    {
      // Retrieve the last stored index in the deque
      let lastSavedIndex = deque[deque.count - 1]
      
      // Check if the last saved value in deque is greater or equal to the current
      // value being processed in the nums array
      if nums[lastSavedIndex] >= nums[currentIndex]
      {
        // Exit the loop since the current number in the window is not a viable candidate
        // to ever be a maximum
        break
      }
      
      // Since the current number in the window is greater than the last value in the deque,
      // remove the last saved index as it will never be a viable candidate to be the maximum
      deque.removeLast()
    }
    
    // Add the current index to the end of the deque
    deque.append(currentIndex)
    
    // Since the first window is the only time we need to check all 'k' numbers, we check to
    // validate that this process is completed successfully
    if currentIndex >= k - 1, !deque.isEmpty,
       let maxIndex = deque.first
    {
      // Append the max of the current window in he max array
      maxArray.append(nums[maxIndex])
    }
  }
  
  return maxArray
}

Finally on average, this is the time I get for the above code on Leetcode

Answer 2

I don’t know how Swift implements arrays, but typically it is expensive to remove the first element. You can, however, use a circular buffer, since you never need to store more than k values in your deque.

You would allocate an array with k elements. You start by populating it with the first k values, and store indices to the first and last element. To pop from the start, increment the first index. To pop from the end, decrement the last index. To append at the end, increment the last index and write the new value. All these increments and decrements are modulo k.

An alternative, much more complex algorithm is by Van Herk, and independently by Gill and Werman. It uses 3 comparisons per output value. https://www.sciencedirect.com/science/article/abs/pii/016786559290069C