Beach House

Concepts Used:

Stack.

Difficulty Level:

Hard.

Problem Statement :

Nishant wants to buy a plot of land, which faces the beach. He will buy only a rectangular plot. So he contacted every owner of the land who has a house facing the beach.
The beach is N units long and each owner has 1 unit (width) of the house facing the beach, and the length of the plot is [i] units (you are given an array).Nishant wants to buy the largest rectangular plot which always has a beach facing side, he can combine two plots and also buy any fractional part of the plot of any owner i.e, if an owner has a[i] units of length, Nishant can buy any length from 1 to a[i] from that owner.Help Nishant find the maximum possible area.

See original problem statement here

Test Case:

Input:
2
5 
3 2 1 4 5
5
4 2 1 3 5

Output:
8
6

Explanation:
Nishant will buy 4 units each from 4th and 5th owner.
Nishant will buy a total of 6 units, from 4th and 5th owner.

Solving Approach:

1.Create an empty stack according to data structures and algorithms.
2.Start from first house, and do following for every house ‘house[i]’ where ‘i’ varies from 0 to n-1.

  1. If stack is empty or house[i] is higher than the house at top of stack, then push ‘i’ to stack.
  2. If this house is smaller than the top of stack, then keep removing the top of stack while top of the stack is greater. Let the removed bar be house[tp]. Calculate area of rectangle with house[tp] as smallest house. For house[tp], the ‘left index’ is previous (previous to tp) item in stack and ‘right index’ is ‘i’ (current index).

3.If the stack is not empty, then one by one remove all houses from stack and do step 2.2 for every removed house.

Solutions:

#include <stdio.h> 
#include <stdlib.h> 
int max(int x,int y)
{
   if(x>y)return x;
   return y;
}
int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
    int n;scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    //for(int i=0;i<n;i++)printf("%d ",a[i]);
    int stack[n];
    int i=-1,j=0,mx=0;
    if(n==1)
    printf("%d\n",a[0]);
    else
    {while(j<n)
    {
      if((i==-1))
      stack[++i]=j++;

      else if(a[stack[i]]<=a[j])
      stack[++i]=j++;
      else
      {
        int x=stack[i];
        //printf("%d ",a[x]);
        i--;
        int area= a[x]*((i==-1)?j:(j-stack[i]-1));
        mx=max(mx,area);
      }
    }
    while(i>=0)
    {
      int x=stack[i];
        i--;
        int area= a[x]*((i==-1)?j:(j-stack[i]-1));
        mx=max(mx,area);
    }
    printf("%d\n",mx);}
  }
  return 0;
}
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> &A) {
int mx=0,mxtop,i=0,tp;
if(A.size()==1) 
return A[0];
stack<int>s; 
while(i<A.size()){
    if(s.empty() or A[s.top()]<=A[i])
    s.push(i++);
    else{ tp=s.top();s.pop();
        mxtop=A[tp]*(s.empty()?i:i-s.top()-1);
        if(mx<mxtop)
        mx=mxtop;
    }
}
while(!s.empty()) 
{
     tp=s.top();s.pop();
        mxtop=A[tp]*(s.empty()?i:i-s.top()-1);
        if(mx<mxtop)
        mx=mxtop;
}
return mx;
}
int main()
{  
int t;
cin>>t;
while(t--)
{
 n;
cin>>n;
vector<int> v;
int x;
for(int i=0;i<n;i++)
{
cin>>x;
v.push_back(x);
}
cout<<solve(v)<<endl;
}
return 0;
}
  import java.util.Scanner;
  import java.util.Stack;

  public class maxHistogramArea {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        int n = scn.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < a.length; i++) {
            a[i] = scn.nextInt();
        }
        System.out.println(solve(a));
    }

    public static int solve(int[] a) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = Integer.MIN_VALUE;
        for (int i = 0; i < a.length;) {
            if (stack.isEmpty() || a[stack.peek()] <= a[i]) {
                stack.push(i);
                i++;
            } else {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    maxArea = Math.max(maxArea, a[top] * i);
                } else {
                    maxArea = Math.max(maxArea, a[top] * (i - stack.peek()-1));
                }
            }
        }
        while (!stack.isEmpty()) {
            int top = stack.pop();
            if (stack.isEmpty()) {
                maxArea = Math.max(maxArea, a[top] * a.length);
            } else {
                maxArea = Math.max(maxArea, a[top] * (a.length - stack.peek()-1));
            }
        }
        return maxArea;
    }

}
Previous post One more GCD sum
Next post Get minimum element from stack

Leave a Reply

Your email address will not be published. Required fields are marked *