PHP Program to Largest Rectangle in Histogram with Explanation
PHP
Hard
PHP Arrays
29 views
1 min read
90 words
This problem helps you practice core PHP fundamentals in a practical way. It builds intuition around largest, rectangle, histogram. Let’s break it down step by step so you can implement it confidently.
Problem Statement
Given bar heights, find the largest rectangle area in the histogram.
Input Format
First n. Next line n heights.
Output Format
One integer area.
Constraints
n
Code Solution
This explanation is written for learning purposes and to help beginners understand the concept clearly.
<?php
$inputText=trim(stream_get_contents(STDIN));
if($inputText==='') exit;
$tokens=preg_split('/\\s+/', $inputText);
$i=0; $n=intval($tokens[$i++] ?? 0);
$h=[];
for($k=0;$k<$n;$k++) $h[] = intval($tokens[$i++] ?? 0);
$st=[];
$best=0;
for($i=0;$i<=$n;$i++){
$cur=($i===$n)?0:$h[$i];
$start=$i;
while($st && $st[count($st)-1][1] > $cur){
[$pos,$height]=array_pop($st);
$best=max($best,$height*($i-$pos));
$start=$pos;
}
$st[] = [$start,$cur];
}
echo $best;
?>
Common Mistakes
- Misreading input/output format.
- Not handling constraints and edge cases.
- Off-by-one errors in loops.
- Forgetting to reset variables between test cases (if any).
Solution Guide
Problem
Given bar heights, find the largest rectangle area in the histogram.
Input / Output
Input
First n. Next line n heights.
Details
Common Mistakes
- Misreading input/output format.
- Not handling constraints and edge cases.
- Off-by-one errors in loops.
- Forgetting to reset variables between test cases (if any).
Official Solution
<?php
$inputText=trim(stream_get_contents(STDIN));
if($inputText==='') exit;
$tokens=preg_split('/\\s+/', $inputText);
$i=0; $n=intval($tokens[$i++] ?? 0);
$h=[];
for($k=0;$k<$n;$k++) $h[] = intval($tokens[$i++] ?? 0);
$st=[];
$best=0;
for($i=0;$i<=$n;$i++){
$cur=($i===$n)?0:$h[$i];
$start=$i;
while($st && $st[count($st)-1][1] > $cur){
[$pos,$height]=array_pop($st);
$best=max($best,$height*($i-$pos));
$start=$pos;
}
$st[] = [$start,$cur];
}
echo $best;
?>
Solutions (0)
No solutions submitted yet. Be the first!
