Problem
LeetCode problem 239. Sliding Window Maximum
You are given an array of integers
nums,
there is a sliding window of sizekwhich is
moving from the very left of the array to the very right.
You can only see theknumbers 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.
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
}
Solution
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
