3
\$\begingroup\$

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 <= 105
• -104 <= nums[i] <= 104
• 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.

Leet code Sliding Window Maximum Brute Force Submission

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: Leet code Sliding Window Maximum Deque Submission

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
}
\$\endgroup\$
3
  • \$\begingroup\$ Do you have some sample input data which exhibits the slow performance? I may write a review, and for the performance aspect it would be nice to have some data for testing (without having it to submit to some forum). \$\endgroup\$
    – Martin R
    Jan 28, 2022 at 17:27
  • \$\begingroup\$ @MartinR - I am not sure how to grab hold of the sample input as the benchmarking happens internally on the leetcode platform. This is the question: leetcode.com/problems/sliding-window-maximum - The only idea I have to get a their large input data set is to write a version that works but is really poor optimally that it will fail on their large data set and they will give you an error "Timed out with this input set" and share the input set with you. \$\endgroup\$ Jan 29, 2022 at 4:46
  • \$\begingroup\$ FYI, another optimization is to reserveCapacity of the maxArray given you know how long that array is going to be. \$\endgroup\$
    – Rob
    Nov 1, 2023 at 16:31

2 Answers 2

1
\$\begingroup\$

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.

Leet code 239. Sliding Window Maximum using Swift

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

Leetcode Sliding Window Maximum using Swift using Deque

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Can you explain how this improved the original code. \$\endgroup\$
    – pacmaninbw
    Dec 14, 2021 at 14:40
  • 2
    \$\begingroup\$ Thanks @MartinR and pacmaninbw for the reminder. A bit new to the format so tried my best to explain now. \$\endgroup\$ Dec 15, 2021 at 12:40
1
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.