Leetcode Sliding Window Maximum problem solution

In this Leetcode Sliding Window Maximum problem solution, 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.

Problem solution in Python.

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        N = len(nums)
        if k == 1:
            return nums
        
        w_start = 0
        w_max = float('-inf')
        all_window_maxes = []
        
        for w_end in range(N):
            w_max = max(w_max, nums[w_end])
            
            if w_end >= k-1:
                all_window_maxes.append(w_max)
                
                if nums[w_start] == w_max:
                    w_max = max(nums[w_start+1:w_end+1])
                w_start += 1
        
        return all_window_maxes

Problem solution in Java.

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        
        int result[] = new int[nums.length - k + 1];
        PriorityQueue<Pair> pq = new PriorityQueue<>();
        int i = 0;
        int j = 0;
        while (j < nums.length) {
            Pair p = new Pair(j, nums[j]);
            pq.add(p);
            if (j - i + 1 < k) {
                j++;
            } else {
                result[i] = pq.peek().val;
                while (!pq.isEmpty() && pq.peek().key < i+1) {
                    pq.remove();
                }
                i++;
                j++;
                
            }

        }
        
        return result;
        
    }
    
    static class Pair implements Comparable<Pair> {

        int key;
        int val;

        Pair(int key, int val) {
            this.key = key;
            this.val = val;
        }

        @Override
        public int compareTo(Pair o) {
            return o.val - this.val;
        }

    }
}

Problem solution in C++.

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int i, n = nums.size();
        vector<int> result;
        multiset<int> mySet;
        
        for(i=0; i<n; i++)
        {
            if(i>=k)
                mySet.erase(mySet.find(nums[i-k]));
            mySet.insert(nums[i]);
            if(mySet.size()>=k)
                result.push_back(*mySet.rbegin());
        }
        
        return result;
    }
};

Problem solution in C.

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize){
    int *result = (int *)calloc(100000, sizeof(int));
    int count = 0;
    int max = INT_MIN;
    int max_idx = 0;
    
    if (numsSize == 0) {
        *returnSize = 0;
        return NULL;
    }
    for (int i = 0; i < k; i++) {
        if (nums[i] > max) {
            max = nums[i];
            max_idx = i;
        }
    }
    result[count++] = max;

    for (int i = 1; i <= (numsSize - k); i++) {
        if (max_idx >= i) {
            if (nums[i + k - 1] > max) {
                max = nums[i + k - 1];
                max_idx = i + k - 1;
            }
            result[count++] = max;
            continue;
        }
        max = INT_MIN;
        for (int j = i; j < i + k; j++) {
            if (nums[j] > max) {
                max = nums[j];
                max_idx = j;
            }
        }
        result[count++] = max;
    }
    *returnSize = count;
    
    return result;
}

coding problems solutions