Given an input array A of integers of size n, and a query array B of integers of size m, find the smallest window of input array that contains all the elements of query array and also in the same order. e.g. input A = [1, 9, 3, 4, 12, 13, 9, 12, 21] B = [9, 12, 21] output A[6..8] = [9, 12, 21]

MinimumWindow.java

package me.ontrait.leetcode.array;

import java.util.*;

public class MinimumWindow {
    public static void main(String[] args) {
        int[] a = {1, 9, 3, 4, 12, 13, 9, 12, 21};
        int[] b = {9, 12, 21};

        System.out.println(minimumWindow(a, b));
    }

    public static int minimumWindow(int[] a, int[] b) {
        if (a.length < b.length) return 0;

        List<Queue<Integer>> pos = new ArrayList<Queue<Integer>>();
        Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
        for(int i = 0; i < b.length; i++) {
            pos.add(new LinkedList<Integer>());
            indexMap.put(b[i], i);
        }

        Queue<Integer> first = pos.get(0);
        Queue<Integer> last = pos.get(pos.size() - 1);
        int start = -1;
        int end = -1;

        int min = Integer.MAX_VALUE;
        for(int i = 0; i < a.length; i++) {
            if (!indexMap.containsKey(a[i])) continue;

            int index = indexMap.get(a[i]);
            pos.get(index).add(i);

            for(int j = index - 1; j >= 0; j--) {
                Queue<Integer> queue = pos.get(j);
                Queue<Integer> pre = pos.get(j + 1);

                while(queue.size() > 1 && queue.peek() < pre.peek()) {
                    queue.remove();
                }
            }

            if (!first.isEmpty() && !last.isEmpty()) {
                int len = last.peek() - first.peek() + 1;
                if (min > len) {
                    min = len;
                    start = first.peek();
                    end = last.peek();
                }
            }
        }

        if (start >= 0) {
            for(int i = start; i <= end; i++) {
                System.out.print(a[i] + " ");
            }
        }
        System.out.println();

        return min;
    }
}