Height of histogram

The histogram is a graphical representation of data in the form of bars or rectangles. each bar corresponds to the range or frequency of data.

package org.wesome.dsalgo;

import java.util.Stack;

public class HistogramHeight {
    public static int histogramHeight(int arr[]) {
        int lengths = arr.length;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int max_area = arr[0];
        int left_smaller[] = new int[lengths];
        int right_smaller[] = new int[lengths];
        for (int i = 0; i < lengths; i++) {
            left_smaller[i] = -1;
            right_smaller[i] = lengths;
        }
        int i = 0;
        while (i < lengths) {
            while (!stack.empty() && stack.peek() != -1 && arr[i] < arr[stack.peek()]) {
                right_smaller[stack.peek()] = i;
                stack.pop();
            }
            if (i > 0 && arr[i] == arr[(i - 1)]) {
                left_smaller[i] = left_smaller[i - 1];
            } else {
                left_smaller[i] = stack.peek();
            }
            stack.push(i);
            i++;
        }
        for (i = 0; i < lengths; i++) {
            max_area = Math.max(max_area, arr[i] * (right_smaller[i] - left_smaller[i] - 1));
        }
        return max_area;
    }
}
package org.wesome.dsalgo;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

public class HistogramHeightTest {
    @Test
    void histogramHeightTest1() {
        int histogramHeights[] = {6, 2, 5, 4, 5, 1, 6};
        Assertions.assertEquals(12, HistogramHeight.histogramHeight(histogramHeights));
    }
}
plugins {
    id 'java'
}

group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8

configurations {
    compileOnly {
        extendsFrom annotationProcessor
    }
}

repositories {
    mavenCentral()
}

dependencies {
    testImplementation 'org.junit.jupiter:junit-jupiter:5.6.2'
}

test {
    useJUnitPlatform()
}

 

follow us on