Java Divide and Conquer: Largest area of a histogram

Question

I am trying to implement a divide and conquer algorithm where you are given an integer array A of size n; all numbers in A are non-negative. A represents a histogram where each bar has width 1 and the i-th bar has height A[i]. My goal is to find the area of the largest rectangle in the histogram that is completely covered by bars. Here is a picture to visualize this: Histogram Area

Here is my code:

 public static int problem(int[] heights) {
        return largestArea(heights, 0, heights.length-1);
    }
    
    private static int largestArea(int[] heights, int low, int high){
        if(low > high) return 0;
        if(low == high) return heights[low];
        int minIndex = findIndexOfMinimumValue(heights, low, high);
        int areaWithMin = (high-low+1) * heights[minIndex];
        int areaLeft = largestArea(heights, low, minIndex-1);
        int areaRight = largestArea(heights, minIndex+1, high);

        return Math.max(areaWithMin, Math.max(areaLeft, areaRight));
    }
    
    private static int findIndexOfMinimumValue(int[] heights, int low, int high){
        int minIndex = low;
        for(int i=low; i<=high; i++)
            if(heights[i] < heights[minIndex])
                minIndex = i;
        return minIndex;
    }

However I am getting a stack overflow error from this line

int areaLeft = largestArea(heights, low, minIndex-1);

https://stackoverflow.com/questions/214741/what-is-a-stackoverflowerror Does this help? — Ewan Brown, Jan 24 '22 at 03:19
@EwanBrown This is helpful, thank you. I am still struggling a bit though with how to solve my particular case. I am a bit new, and not the quickest with Java. — Psycho Bunnies, Jan 24 '22 at 03:24

Aditya Arora · Answer 1 · 2022-01-24T06:05:16.360

Sorry for being late, I had my online class.

Here's my non recursive approach :

public static int getLargestArea(int[] histogram) {
    if(histogram.length == 0) return 0;
    if(histogram.length == 1) return histogram[0];
    int max = 0;
    for(int i = 0; i < histogram.length; i++) {
        int area = findAreaOf(histogram, i);
        if(max ‹ area)  max = area;
    }
    return max; 
}
private static int findAreaOf(int[] histogram,  int index) {

    //Find area left to index. 
    int leftArea = 0;
    for(int i = index - 1; i >= 0; i--) {
        if(histogram[i] < histogram[index]) break; 
        leftArea += histogram[index]:
    }

    //Find area right to index. 
    int rightArea = 0;
    for(int i = index + 1; i < histogram.length; i++) {
        if(histogram[i] < histogram[index]) break; 
        rightArea += histogram[index]:
    }

    return histogram[index] + leftArea + rightArea;
}

Java Divide and Conquer: Largest area of a histogram

1 Answers1