Question 24 : Sliding window maximum in java

Given an array of integers and a window size k, move the window from left to right and return the maximum number in each window.

For example:

nums = [1,3,-1,-3,5,3,6,7]
k = 3

 [1  3  -1] → 3
 1 [3  -1  -3] → 3
 1  3 [-1  -3  5] → 5
 1  3  -1 [-3  5  3] → 5
 1  3  -1  -3 [5  3  6] → 6
 1  3  -1  -3  5 [3  6  7] → 7Output  - [3, 3, 5, 5, 6, 7]

Solution

Naive Approach Brute force (scan all windows) :

• The basic solution would be just generating all the contiguous subarrays of size k and looping over them for finding out the max in that current subarray.
• Considering, for every spot we are basically taking next ‘k’ element and then we loop over those k elements, so the worst time complexity of this algorithm would be O(n*k).

import java.util.Scanner;
 
public class slidingWindowMax {
 
    public static void main(String[] args) {
 
        Scanner scn = new Scanner(System.in);
        int [] arr = new int[scn.nextInt()];
 
        for(int i = 0; i < arr.length; i++)
        {
            arr[i] = scn.nextInt();
        }
 
        int windowSize = scn.nextInt();
 
        solve(arr, windowSize);
 
    }
 
    public static void solve(int[] arr, int k)
    {
        // starting the outer loop from k and running it until, 
                // current pointer is EQUAL to arr.length
        for(int i = k; i <= arr.length; i++)
        {
            int max = Integer.MIN_VALUE;
 
            // this loop considers subarrays of size k ending at i-1
            for(int j = i-k; j<i; j++)
            {
                max = Math.max(max, arr[j]);
            }
 
            System.out.println(max);
        }
    }

}

Python code 

def local_min_bruteforce(arr):
    n = len(arr)

    for i in range(n):
        is_min = True
        for j in range(n):
            if i != j and arr[j] < arr[i]:
                is_min = False
                break
        if is_min:
            return i
    return -1

print(local_min_bruteforce([9,6,3,14,5,7,4]))

Slightly Efficient Approach Binary Search Local Minima

public class LocalMinimaBinarySearch {

    public static int findLocalMin(int[] arr, int low, int high) {
        int n = arr.length;
        int mid = low + (high - low) / 2;

        // Check if mid is local minima
        boolean leftOk = (mid == 0) || (arr[mid] < arr[mid - 1]);
        boolean rightOk = (mid == n - 1) || (arr[mid] < arr[mid + 1]);

        if (leftOk && rightOk) {
            return mid;
        }

        // If left neighbor is smaller, go left
        if (mid > 0 && arr[mid - 1] < arr[mid]) {
            return findLocalMin(arr, low, mid - 1);
        }

        // Else go right
        return findLocalMin(arr, mid + 1, high);
    }

    public static void main(String[] args) {
        int[] arr = {9, 6, 3, 14, 5, 7, 4};
        int index = findLocalMin(arr, 0, arr.length - 1);
        System.out.println("Local Minima index: " + index);
    }
}

Python code

def find_local_min(arr, low, high):
    n = len(arr)
    mid = (low + high) // 2

    left_ok = (mid == 0) or (arr[mid] < arr[mid - 1])
    right_ok = (mid == n - 1) or (arr[mid] < arr[mid + 1])

    if left_ok and right_ok:
        return mid

    if mid > 0 and arr[mid - 1] < arr[mid]:
        return find_local_min(arr, low, mid - 1)

    return find_local_min(arr, mid + 1, high)


arr = [9, 6, 3, 14, 5, 7, 4]
print(find_local_min(arr, 0, len(arr) - 1))

Most Efficient Approach Java — Deque Approach (O(n))

In this approach we use Deque which helps us finding the sliding window maximum in O(n).

• A Deque is basically a queue which is open on both the ends for both enqueue and Deque, that is, you can add or remove element either from front or rear.

What we actually do to solve the problem is:

we keep the k elements of the subarrays in the reverse sorted order, We need not keep all the k elements though which we will see later in code.

• Generate the Deque for the first k elements, keeping them sorted in reverse order so that the maximum element is at the front.
• If the Deque is empty, add the element straightaway, else check if the incoming element is greater than the last element, if it is, keep popping the elements from last until the last element of the remaining Deque is greater than the incoming element.
• We also need to remove the elements which belong to different subarray. i.e the indices in the Deque must be in the range, [i, i+k].

An element will only be removed on two conditions :
(i) If the upcoming element is greater than the element at rear, if it, it will keep on popping the element until there comes a larger element at rear of remaining dequeue because we need to keep the array sorted in the reverse order.
(ii) If the element belongs to any other subarray then there is no point in keeping it.

import java.util.LinkedList;
import java.util.Scanner;
 
public class SlidingWindowMax {
 
    static int[] sarr;
 
    public static void main(String[] args) {
 
        Scanner scn = new Scanner(System.in);
        int[] arr = new int[scn.nextInt()];
 
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scn.nextInt();
        }
 
        System.out.print("arr[]: {");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(" "+arr[i]);
        }
 
        System.out.println(" }");
 
        int windowSize = scn.nextInt();
 
        solveEfficient(arr, windowSize);
 
    }
 
    public static void solveEfficient(int[] arr, int k) {
        LinkedList<Integer> deque = new LinkedList<>();
 
        for (int i = 0; i < arr.length; i++) {
 
            /* keep removing the elements from deque 
             * which are smaller than the current element, 
             * because we need to keep our deque sorted in dec order 
             */
            while (!deque.isEmpty() && arr[deque.getLast()] <= arr[i]) {
                deque.removeLast();
            }
 
            /* removing the i-k element, because that element does not belong 
             * to the subarray we are currently working on.
             */
            while (!deque.isEmpty() && deque.getFirst() <= i - k) {
                deque.removeFirst();
            }
 
            deque.addLast(i);
 
            if(i >= k-1)
            {   
            /* only print when we have processed atleast k elements 
             * to make the very first subarray
             */
                System.out.print(" "+arr[deque.getFirst()]);
            }
 
        }
    }
}

Python Code

def find_local_min(arr, low, high):
    n = len(arr)
    mid = (low + high) // 2

    left_ok = (mid == 0) or (arr[mid] < arr[mid - 1])
    right_ok = (mid == n - 1) or (arr[mid] < arr[mid + 1])

    if left_ok and right_ok:
        return mid

    if mid > 0 and arr[mid - 1] < arr[mid]:
        return find_local_min(arr, low, mid - 1)

    return find_local_min(arr, mid + 1, high)


arr = [9, 6, 3, 14, 5, 7, 4]
print(find_local_min(arr, 0, len(arr) - 1))

  
    
    
    
    
  

  

    
Approach
    
Time Complexity
    
Space Complexity
    
Best Use
  

  

    

      Deque (Sliding Window Optimal)
    
    

      O(n)
    
    

      O(k)
    
    

      ⭐ Best & scalable
    
  

  

    

      Max heap per window
    
    

      O(n log k)
    
    

      O(k)
    
    

      ✔ Good for k small
    
  

  

    

      Brute force (scan all windows)
    
    

      O(n × k)
    
    

      O(1)
    
    

      ❌ Too slow