HackerRank Largest Rectangle Interview preparation kit solution

In this HackerRank Largest Rectangle Interview preparation kit problem you need to Complete the function largestRectangle. It should return an integer representing the largest rectangle that can be formed within the bounds of consecutive buildings.

Problem solution in Python programming.

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the largestRectangle function below.
def largestRectangle(h):
    h += [0]
    s = []
    ma = 0
    for i in range(0, len(h)):
        j = i
        while len(s) > 0 and s[-1][0] >= h[i]:
            val, j = s.pop()
            ma = max(ma, (i - j) * val)
        s.append([h[i], j])
    return ma

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input())

    h = list(map(int, input().rstrip().split()))

    result = largestRectangle(h)

    fptr.write(str(result) + '\n')

    fptr.close()

Problem solution in Java Programming.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;


public class Solution
{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 64 * 1024);

        final int N = Integer.parseInt(br.readLine().trim(), 10);
        final String[] data = br.readLine().trim().split(" ");
        final long[] hist = new long[N];

        for (int i = 0; i < N; i++) {
            final long v = Long.parseLong(data[i], 10);
            hist[i] = v;
        }

        long res0 = 0L;
        for (int i = 0; i < N; i++) {
            int idx0 = i;
            for (; idx0 >= 1; idx0--) {
                if (hist[idx0 - 1] < hist[i]) {
                    break;
                }
            }
            int idx1 = i;
            for (; idx1 < hist.length - 1; idx1++) {
                if (hist[idx1 + 1] < hist[i]) {
                    break;
                }
            }
            final long area = hist[i] * (idx1 - idx0 + 1);
            if (area > res0) {
                res0 = area;
            }
        }
        System.out.println(res0);


        br.close();
        br = null;
    }
}

Problem solution in C++ programming.

#include <stack>
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int N, h[100005];
int p = 1, s[100005];
int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i) scanf("%d", &h[i]);
    int ans = 0;
    for (int i = 0; i < N + 2; ++i) {
        while (h[i] < h[s[p - 1]]) {
            int y = h[s[p - 1]];
            p--;
            ans = max(ans, (i - s[p - 1] - 1) * y);
        }
        s[p++] = i;
    }
    printf("%d\n", ans);
    return 0;
}

Problem solution in C programming.

#include <stdio.h>
#define SIZ 100000
int m[SIZ+1];
long long st[SIZ];

int main(){
	int N,j,ptr;
	long long r,h;
	scanf("%d",&N);
		for(j=0;j<N;j++)scanf("%d",m+j);m[j]=0;
		for(r=ptr=j=0;j<=N;j++){
			int left=j;
			for(;ptr && (h=st[ptr-1]>>32)>m[j];){
				int l=st[--ptr]&0xffffffff;
				if(r<h*(j-l))r=h*(j-l);
				left=l;
			}
			st[ptr++]=((long long)m[j]<<32)|left;
		}
		printf("%lld\n",r);
	return 0;
}

Problem solution in JavaScript programming.

function processData(input) {
    var lines = input.split('\n'),
        n = parseInt(lines[0]),
        buildings = lines[1].split(' ').map(function(elem){
            return parseInt(elem);
        });
    var areaAt = function(k) {
        var height = buildings[k],
            area = height,
            left = k-1,right = k+1;
        //calculate to left
        for(; left > -1 && buildings[left] >= height; left--, area+=height);
        //calculate to right
        for(; right < buildings.length && buildings[right] >= height; right++, area+=height);
        return area;
    };
    var maxArea = areaAt(0),
        lastHeight = buildings[0];
    for(var i = 1, curHeight = buildings[i]; i < n; lastHeight = buildings[i],i++, curHeight = buildings[i]) {
        if(curHeight !== lastHeight) {
            var area = areaAt(i);
            if(area > maxArea) {
                maxArea = area;
            }
        }
    }
    console.log(maxArea);
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});