Interval Minimum Number

Interval Minimum Number

25%

Accepted

Given an integer array (index from 0 to n-1, where n is the size of this array), and an query list. Each query has two integers [start, end]. For each query, calculate the minimum number between index start and end in the given array, return the result list.

Have you met this question in a real interview? 

Yes

Example

For array [1,2,7,8,5], and queries [(1,2),(0,4),(2,4)], return[2,1,5]

Note

We suggest you finish problem Segment Tree Build, Segment Tree Queryand Segment Tree Modify first.

Challenge

O(logN) time for each query

/**

 * Definition of Interval:

 * public classs Interval {

 *     int start, end;

 *     Interval(int start, int end) {

 *         this.start = start;

 *         this.end = end;

 *     }

 */

public class Solution {

    public ArrayList<Integer> intervalMinNumber(int[] A, 

                                                ArrayList<Interval> queries) {

        ArrayList<Integer> res = new ArrayList<Integer>();

        MinSegmentTree root = buildTree(A, 0, A.length-1);

        for(Interval interval : queries){

            res.add(getValue(root, interval.start, interval.end));

        }

        return res;

       

    }

    

    private int getValue(MinSegmentTree root, int start, int end){

        if(root == null || start > root.end || end < root.start) return Integer.MAX_VALUE;

        if(root.start == root.end || (start <= root.start && end >= root.end)) return root.min;

        

        return Math.min(getValue(root.left, start, end), getValue(root.right, start, end));

    }

    

    private MinSegmentTree buildTree(int[] A, int from, int to){

        if(from > to) return null;

        if(from == to) return new MinSegmentTree(from, to, A[from]);

        MinSegmentTree root = new MinSegmentTree(from, to);

         root.left = buildTree(A, from, (from + to) / 2);

         root.right = buildTree(A, (from+to)/2+1, to);

        if(root.left != null && root.right != null){

            root.min = Math.min(root.left.min, root.right.min);

        } else if(root.left != null){

            root.min = root.left.min;

        } else {

            root.min = root.right.min;

        }

        return root;

        

    }

    class MinSegmentTree{

        int start;

        int end;

        int min = Integer.MAX_VALUE;

        MinSegmentTree left;

        MinSegmentTree right;

        

        public MinSegmentTree(int start, int end){

            this.start = start;

            this.end = end;

        }

        

         public MinSegmentTree(int start, int end, int min){

            this(start, end);

            this.min = min;

        }

    }

}