239. Sliding Window Maximum

Problem Statement

link: https://leetcode.com/problems/product-of-array-except-self/ https://leetcode.cn/problems/product-of-array-except-self/

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example:

Input: nums = [1,2,3,4] Output: [24,12,8,6]

Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]

Solution Approach

The solution approach is to compute the product of all elements in the input array except the current element in O(n) time without using division.

Algorithm

1. Initialize left and right arrays to store products to the left and right of each element.
2. Calculate left products by iterating through the input array, maintaining a running product to the left.
3. Calculate right products by iterating through the input array in reverse order, maintaining a running product to the right.

Implement

    class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = deque()
        res = []
        n = len(nums)
        for i in range(n):
            while q and nums[q[-1]] < nums[i]:
                q.pop()
            q.append(i)
            if q[0] == i - k:
                q.popleft()
            if i >= k - 1:
                res.append(nums[q[0]])
        return res
       

    
    

Twitter  facebook  Email