Just for Fun as I came across this same question again

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * User: huzhou
 * Date: 10/18/12
 * Time: 10:28 PM
 * To change this template use File | Settings | File Templates.
 */
public class FindLargestRectangle {

    /**
     * a simple model of Rectangle using [left, right, height] in a XY based area
     */
    public static class Rectangle implements Comparable {
        private final int _left;//inclusive
        private final int _right;//exclusive
        private final int _height;

        public Rectangle(final int left, final int right, final int height){
            _left = left;
            _right = right;
            _height = height;
        }

        public int getLeft(){
            return _left;
        }

        public int getRight(){
            return _right;
        }

        public int getHeight(){
            return _height;
        }

        public int getArea(){
            return _height * (_right - _left);
        }

        @Override
        public int compareTo(final Rectangle other) {//find out which one is larger
            return getArea() - other.getArea();
        }

        @Override
        public String toString(){
            return String.format("left=%d&right=%d&height=%d&area=%d\n", _left, _right, _height, getArea());
        }
    }

    /**
     * @param heights
     * @return
     */
    public static Rectangle findLargestAreaRectangle(final int[] heights){
        if(heights == null || heights.length == 0){
            throw new IllegalArgumentException("heights array cannot be null or empty");
        }
        final int length = heights.length;

        //this is O(n) init
        final List indexesOfSortedHeights = new ArrayList(length);
        for(int i = 0; i < length; i++){
            indexesOfSortedHeights.add(Integer.valueOf(i));
        }
        //this will help us to sort the indexes of heights in ASCENDING order (by heights), O(n*log(n)) as sorting is O(n*log(n)) and map init is O(n)
        Collections.sort(indexesOfSortedHeights, new Comparator() {
            @Override
            public int compare(final Integer left, final Integer right) {
                return heights[left.intValue()] - heights[right.intValue()];
            }
        });

        //delegate to the actual implementation (recursion)
        return findLargestAreaRectangle(indexesOfSortedHeights.iterator(),
                heights,
                new BitSet(length),
                new Rectangle(0, 0, 0));
    }

    protected static Rectangle findLargestAreaRectangle(final Iterator nextIndexOfLowestHeight,
                                                 final int[] heights,
                                                 final BitSet indexes,
                                                 final Rectangle largestTillNow){
        //end of story
        if(!nextIndexOfLowestHeight.hasNext()){
            return largestTillNow;
        }

        //pop next lowest height's index
        final int indexOfLowestHeight = nextIndexOfLowestHeight.next().intValue();
        nextIndexOfLowestHeight.remove();

        final int valueOfLowestHeight = heights[indexOfLowestHeight];
        final int left = getLeftBoundary(indexes, indexOfLowestHeight);
        final int right = getRightBoundary(indexes, indexOfLowestHeight, heights.length);
        //update the indexes, this will affect the recursive boundary discovers
        indexes.set(indexOfLowestHeight);

        final Rectangle thisRectangle = new Rectangle(left, right, valueOfLowestHeight);
        final Rectangle largestRectangle = thisRectangle.compareTo(largestTillNow) > 0 ? thisRectangle : largestTillNow;

        //recursively look for the largest using next lowest height
        return findLargestAreaRectangle(nextIndexOfLowestHeight, heights, indexes, largestRectangle);
    }

    //find the left boundary
    private static int getLeftBoundary(BitSet indexes, int indexOfLowestHeight) {
        //this finds the closest index set to the left of indexOfLowestHeight
        //well, jdk7 would have BitSet#previousSetBit
        int left = indexes.nextSetBit(0);
        for(int i = left; i >= 0 && i < indexOfLowestHeight; i = indexes.nextSetBit(i + 1)){
            left = i;
        }
        left = left < 0 ? 0 : left + 1;//if no index set to its left, we'll use 0 (left most), otherwise we'll use left + 1
        return left;
    }

    //find the right boundary
    private static int getRightBoundary(BitSet indexes, int indexOfLowestHeight, int length) {
        //this finds the closest index set to the right of indexOfLowestHeight
        final int right = indexes.nextSetBit(indexOfLowestHeight);
        return right < 0 ? length : right;//if no index set to its right, we'll use length (as it's exclusive)
    }

    public static void main(String[] args){
        final int[] singleHeight = {9};
        System.out.println(findLargestAreaRectangle(singleHeight));

        final int[] doubleHeights = {1, 9};
        System.out.println(findLargestAreaRectangle(doubleHeights));

        final int[] doubleHeightsTwo = {9, 5};
        System.out.println(findLargestAreaRectangle(doubleHeightsTwo));

        final int[] multipleHeights = {9, 3, 4, 5};//12
        System.out.println(findLargestAreaRectangle(multipleHeights));

        final int[] multipleHeightsTwo = {3, 7, 9, 4};//12, 14, 9, 12
        System.out.println(findLargestAreaRectangle(multipleHeightsTwo));

        final int[] manyHeights = {3, 32, 12, 18, 91, 78, 47, 56, 17, 25, 19};
        System.out.println(findLargestAreaRectangle(manyHeights));
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s