Algorithm


Problem Name: Data Structures - Largest Rectangle

Problem Link: https://www.hackerrank.com/challenges/largest-rectangle/problem?isFullScreen=true

In this HackerRank in Data Structures - Largest Rectangle solution

Skyline Real Estate Developers is planning to demolish a number of old, unoccupied buildings and construct a shopping mall in their place. Your task is to find the largest solid area in which the mall can be constructed.

There are a number of buildings in a certain two-dimensional landscape. Each building has a height, given by h[i] where i epsolunot [1,n] . If you join k adjacent buildings, they will form a solid rectangle of area

k * min(h[i],h[i + 1] , ... , h(i +k -1).

Example

h = [3,2,3]

A rectangle of height h = 2 and length k = 3 can be constructed within the boundaries. The area formed is h * k = 2 * 3 = 6.

Function Description

 

Complete the function largestRectangle int the editor below. It should return an integer representing the largest rectangle that can be formed within the bounds of consecutive buildings.

 

largestRectangle has the following parameter(s):

 

  • int h[n]: the building heights

 

Returns
- long: the area of the largest rectangle that can be formed within the bounds of consecutive buildings

Input Format

The first line contains n the number of buildings.
The second line contains n space-separated integers, each the height of a building.

Constraints

  • 1 <= n <= 10**5
  • 1 <= h[i] <= 10**6

Sample Input

STDIN       Function
-----       --------
5           h[] size n = 5
1 2 3 4 5   h = [1, 2, 3, 4, 5]

Sample Output

9

Explanation

An illustration of the test case follows.
image

 

 

 

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* readline();
char* ltrim(char*);
char* rtrim(char*);
char** split_string(char*);

int parse_int(char*);

/*
 * Complete the 'largestRectangle' function below.
 *
 * The function is expected to return a LONG_INTEGER.
 * The function accepts INTEGER_ARRAY h as parameter.
 */

long largestRectangle(int h_count, int* h) {
  
    long area, max_area = 0;
    int i,j, left, right;
    for(i=0;i < h_count;i++) {
        
        // get left 
        j=i-1;
        left = 0, right = 0, area = 0;
        while(j>=0 && (h[j]>= h[i])){
            left++;
            j--;
        }
        
        // get right
        j = i+1;
        while(j < h_count && (h[j] >= h[i])){
            right++;
            j++;
        }
        
        area = h[i]*(left+right+1);
        max_area = (max_area>area)?max_area:area;
        
    }
    
    return max_area;
}

int main()
{
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    int n = parse_int(ltrim(rtrim(readline())));

    char** h_temp = split_string(rtrim(readline()));

    int* h = malloc(n * sizeof(int));

    for (int i = 0; i  <  n; i++) {
        int h_item = parse_int(*(h_temp + i));

        *(h + i) = h_item;
    }

    long result = largestRectangle(n, h);

    fprintf(fptr, "%ld\n", result);

    fclose(fptr);

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;

    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) {
            break;
        }

        data_length += strlen(cursor);

        if (data_length  <  alloc_length - 1 || data[data_length - 1] == '\n') {
            break;
        }

        alloc_length <<= 1;

        data = realloc(data, alloc_length);

        if (!data) {
            data = '\0';

            break;
        }
    }

    if (data[data_length - 1] == '\n') {
        data[data_length - 1] = '\0';

        data = realloc(data, data_length);

        if (!data) {
            data = '\0';
        }
    } else {
        data = realloc(data, data_length + 1);

        if (!data) {
            data = '\0';
        } else {
            data[data_length] = '\0';
        }
    }

    return data;
}

char* ltrim(char* str) {
    if (!str) {
        return '\0';
    }

    if (!*str) {
        return str;
    }

    while (*str != '\0' && isspace(*str)) {
        str++;
    }

    return str;
}

char* rtrim(char* str) {
    if (!str) {
        return '\0';
    }

    if (!*str) {
        return str;
    }

    char* end = str + strlen(str) - 1;

    while (end >= str && isspace(*end)) {
        end--;
    }

    *(end + 1) = '\0';

    return str;
}

char** split_string(char* str) {
    char** splits = NULL;
    char* token = strtok(str, " ");

    int spaces = 0;

    while (token) {
        splits = realloc(splits, sizeof(char*) * ++spaces);

        if (!splits) {
            return splits;
        }

        splits[spaces - 1] = token;

        token = strtok(NULL, " ");
    }

    return splits;
}

int parse_int(char* str) {
    char* endptr;
    int value = strtol(str, &endptr, 10);

    if (endptr == str || *endptr != '\0') {
        exit(EXIT_FAILURE);
    }

    return value;
}

Copy The Code & Try With Live Editor

#2 Code Example with Java Programming

Code - Java Programming


import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'largestRectangle' function below.
     *
     * The function is expected to return a LONG_INTEGER.
     * The function accepts INTEGER_ARRAY h as parameter.
     */

    public static long largestRectangle(List < Integer> h) {
    h.add(0);
    long answer = 0;
    Stack < Integer> s = new Stack<>();
    for (int i = 0; i  <  h.size(); i++) {
        while (!s.isEmpty() && h.get(s.peek()) >= h.get(i)) {
            long height = h.get(s.pop());
            long width = s.isEmpty() ? i : (i - s.peek() - 1);
            answer = Math.max(answer, height * width);
        }
        s.push(i);
    }
    return answer;
}

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int n = Integer.parseInt(bufferedReader.readLine().trim());

        List < Integer> h = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
            .map(Integer::parseInt)
            .collect(toList());

        long result = Result.largestRectangle(h);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}
Copy The Code & Try With Live Editor

#5 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);
vector < string> split(const string &);

/*
 * Complete the 'largestRectangle' function below.
 *
 * The function is expected to return a LONG_INTEGER.
 * The function accepts INTEGER_ARRAY h as parameter.
 */

long largestRectangle(vector<int> h) {
    stack < int> st;
    int area=0;
    int i=0;
    // insert values in front of back for an initial comparison.
    // INT_MIN guarantees first index will be added to the stack
    // and guarantees last index will be a "decrease", prompting to check the stack for area.
    h.insert(h.begin(), INT_MIN);
    h.insert(h.end(), INT_MIN);
    
    while (i  <  h.size()){
        //if h[i] starts to decrement,
        //pop stack without increasing i and calculate the area
        // R is the value we havent added yet
        // L is the value 2nd to front of stack
        // L and R are the closest indices which have heights lower than st.top()
        if (!st.empty() && h[i] < h[st.top()]){
            int R=i;
            int heightIndex=st.top();
            st.pop();
            int L=st.top();
            int width = R - L - 1;
            area=max(area, h[heightIndex]*width);
        } else {
            // add index of incrementing heights to stack
            st.push(i);
            i++;
        }
    }
    return area;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string n_temp;
    getline(cin, n_temp);

    int n = stoi(ltrim(rtrim(n_temp)));

    string h_temp_temp;
    getline(cin, h_temp_temp);

    vector < string> h_temp = split(rtrim(h_temp_temp));

    vector<int> h(n);

    for (int i = 0; i  <  n; i++) {
        int h_item = stoi(h_temp[i]);

        h[i] = h_item;
    }

    long result = largestRectangle(h);

    fout << result << "\n";

    fout.close();

    return 0;
}

string ltrim(const string &str) {
    string s(str);

    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), not1(ptr_fun < int, int>(isspace)))
    );

    return s;
}

string rtrim(const string &str) {
    string s(str);

    s.erase(
        find_if(s.rbegin(), s.rend(), not1(ptr_fun < int, int>(isspace))).base(),
        s.end()
    );

    return s;
}

vector < string> split(const string &str) {
    vector<string> tokens;

    string::size_type start = 0;
    string::size_type end = 0;

    while ((end = str.find(" ", start)) != string::npos) {
        tokens.push_back(str.substr(start, end - start));

        start = end + 1;
    }

    tokens.push_back(str.substr(start));

    return tokens;
}
Copy The Code & Try With Live Editor

#3 Code Example with Python Programming

Code - Python Programming


#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'largestRectangle' function below.
#
# The function is expected to return a LONG_INTEGER.
# The function accepts INTEGER_ARRAY h as parameter.
#

def largestRectangle(heights):
    maxera = 0
    stack  = [] # (i,h)
    for i,h in enumerate(heights):
        start = i
        while stack and stack[-1][1] > h:
            index , height = stack.pop()
            maxera = max(maxera, (i-index)*height)
            start = index
        stack.append((start, h))
    for i, h in stack:
        maxera = max(maxera,h*(len(heights)-i))
    return maxera

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

    n = int(input().strip())

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

    result = largestRectangle(h)

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

    fptr.close()

Copy The Code & Try With Live Editor

#4 Code Example with Javascript Programming

Code - Javascript Programming


'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the 'largestRectangle' function below.
 *
 * The function is expected to return a LONG_INTEGER.
 * The function accepts INTEGER_ARRAY h as parameter.
 */

function largestRectangle(hs) {
  let max = 0
  hs.forEach((h, i) => {
    let w = 1, j = i + 1, k = i - 1
    while (hs[j] >= h && j  <  hs.length) w++, j++
    while (hs[k] >= h && k >= 0) w++, k--
    if (h * w > max) max = h * w
  })
  return max
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const n = parseInt(readLine().trim(), 10);

    const h = readLine().replace(/\s+$/g, '').split(' ').map(hTemp => parseInt(hTemp, 10));

    const result = largestRectangle(h);

    ws.write(result + '\n');

    ws.end();
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Game of Two Stacks solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Simple Text Editor solution in Hackerrank - Hacerrank solution C, C++, java,js, Python, PHP