Java : Finding subarray from input array containing all integers in query array

Problem : Given an input array of integers of size n, and a query array of integers of size k, find the smallest window of input array that contains all the elements of query array and also in the same order. (reference : http://www.careercup.com/question?id=3655770)

Solution :

a.) find all indexes in input array with start and end as provided in query array

b.) calculate average at each iteration and save in array(in place, no extra memory needed) for query array

c.) for each index found in input array, calculate average similar in step(b)

d.) for each element in query array and index for which average is calculated, calculate average again at each step and match with corresponding value in query array at that iteration, if all value match, you have the index and subarray 🙂

I have tried writing a java program, I hope it helps others as well

 /*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package careercup.google;

import java.util.ArrayList;
import java.util.Iterator;

/**
 *
 * @author Harit
 */
public class ArraySubArrayFind {
    private static float[] query;
    private static float[] from;
    private static ArrayList<Integer> start_index = new ArrayList<Integer>();

    public static void main(String args[]){

        /* ----- Input Sample ------ */
        //query = new float[]{3,-5,6};
        //from = new float[]{-1,2,3,-5,6,-2};
        query = new float[]{2,3,5};
        //from = new float[]{2,4,2,6,2,3,2,3,5,2};
        //from = new float[]{2,4,2,6,2,3,2,3,1,2};
        from = new float[]{2,3,5,2,5,5,3,2,3,5,2};
        /* -------------------------- */

        for(int i=0; i<from.length; i++){
            if(from[i] == query[0]){
                int offset = i + (query.length-1);
                if(offset > (from.length-1)){
                    /* end of array, subarray couldn't be found */
                    continue;
                }
                if(from[offset] != query[query.length-1]){
                    continue;
                }
                start_index.add(i);
            }
        }

        /* calculating average for query array */
        calculateAverage(query,0);

        boolean found = false;
        Iterator iter = start_index.iterator();
        while(iter.hasNext()){
            int index = Integer.parseInt(iter.next().toString());
            calculateAverage(from, index);
            if(verify(query, from, index)){
                System.out.println("Subarray exists at index : " + index);
                found = true;
                continue;
            }
        }
        if(!found){
            System.out.println("Subarray doesn't exists");
        }
    }

    private static void calculateAverage(float[] array, int start){
        float last_sum = 0;
        int total_num = 0;

        for(int i=start; i<(start + query.length); i++){
            if(i==0){
                last_sum = array[i];
                total_num = 1;
            }else{
                last_sum += array[i];
                total_num += 1;
            }
            array[i] = (last_sum/total_num);
        }
    }

    private static boolean verify(float[] array_one, float[] array_two, int index){
        /* Note : array_one has to be smaller array i.e. query array");*/
        for(int i = 0; i<array_one.length; i++){
            if(((array_one[i] + array_two[index + i])/2) != array_one[i]){
                return false;
            }
        }
        return true;
    }
}

output:
run:
Subarray exists at index : 0
Subarray exists at index : 7
BUILD SUCCESSFUL (total time: 0 seconds)