1-Liner (Brute Force)

  • 3

    Linear time is only the follow-up question, so... here's an accepted Python O(kn) one-liner:

    def maxSlidingWindow(self, nums, k):
        return nums and [max(nums[i:i+k]) for i in range(len(nums)-k+1)]

    In Ruby it's even shorter, but unfortunately too slow to get accepted.

    def max_sliding_window(nums, k)
        k > 0 ? nums.each_cons(k).map(&:max) : []

    Of course I also wrote normal O(n) solutions. I'm wondering, though, whether the above could be made fast with still simple code. I'm particularly interested in Ruby, as the above isn't accepted. Here's a sketch:

    Let's say we have 1000 numbers and k is 500. The above brute force method finds the maximum of each window simply by looking at the window's 500 elements. What if we instead split the 1000 numbers into 50 streaks of 20 numbers each, and precompute the maximum of each streak? Then for each window, we only have to maximize over ~25 streak maximums and 20 elements.

Log in to reply

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