Interval Minimum Number

LintCode-205.Interval Minimum Number

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.

Example

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

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 {
    /**
     *@param A, queries: Given an integer array and an query list
     *@return: The result list
     */
    public ArrayList<Integer> intervalMinNumber(int[] A, 
                                                ArrayList<Interval> queries) {
        if (A == null || A.length == 0 
            || queries == null || queries.size() == 0) {
            return new ArrayList<Integer>();        
        }
        
        SegmentTreeNode root = buildTree(0, A.length - 1, A);
        
        ArrayList<Integer> result = new ArrayList<Integer>();
        for (Interval interval : queries) {
            int min = query(root, interval.start, interval.end);
            result.add(min);
        }
        
        return result;
    }
    
    int query(SegmentTreeNode node, int start, int end) {
        if (node == null) {
            return 0;
        }
    
        if (start <= node.start && end >= node.end) {
            return node.min;
        }
        
        int middle = node.start + (node.end - node.start) / 2;
        
        if (end <= middle) {
            return query(node.left, start, end);
        } else if (start > middle) {
            return query(node.right, start, end);
        } else {
            return Math.min(query(node.left, start, middle), query(node.right, middle + 1, end));
        }
    }
    
    SegmentTreeNode buildTree(int start, int end, int[] A) {
        if (start > end) {
            return null;
        }
        
        SegmentTreeNode node = new SegmentTreeNode(start, end);
        
        if (start != end) {
            int middle = start + (end - start) / 2;
            
            node.left = buildTree(start, middle, A);
            node.right = buildTree(middle + 1, end, A);
            
            node.min = Math.min(node.left.min, node.right.min);
        } else {
            node.min = A[start];
        }
        
        return node;
    }
}

class SegmentTreeNode {
    int start, end;
    int min;
    SegmentTreeNode left;
    SegmentTreeNode right;
    
    public SegmentTreeNode(int start, int end) {
        this.start = start;
        this.end = end;
        this.min = 0;
        this.left = this.right = null;
    }
}

Hope this helps,
Michael