Last active
November 1, 2020 19:51
-
-
Save Ch-sriram/d3d730523c96bed2dbff1f8c6103d16c to your computer and use it in GitHub Desktop.
Area of Container with the Most Amount of Water [TC: O(N); SC: O(N)]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Problem Link: https://i.ibb.co/hVT71cp/Container-with-most-water.png | |
// Test Link: https://ide.geeksforgeeks.org/OBtxHYttjP | |
// Solution Status: Could not find this particular problem anywhere on any online judge | |
#include <stack> | |
#include <vector> | |
#include <climits> | |
#include <iostream> | |
#include <algorithm> | |
using namespace std; | |
// Time Complexity: O(N) | |
void emptyTheStack(stack<pair<int, int>> &s, vector<int> &FS, int sentinal) { | |
while(!s.empty()) { | |
FS[s.top().second] = sentinal; | |
s.pop(); | |
} | |
} | |
// Time: O(4N); Space: O(3N) | |
int findMaxRectangularArea(vector<int> &heights, const int n) { | |
// STEP 2: Find the set of buildings (parallel to each other) which cover the max rectangular area => container. | |
// To find the largest rectangular area, we need to find the First Smaller (not smallest) Building to a | |
// building 'i', both on the left side and right side. | |
// For that, we can use a stack to know the First Smaller Building on the left from building 'i', denoted | |
// as FSL[i]. And similarly, we can find FSR[i] denoting the First Smaller Building on the right from | |
// building 'i'. | |
stack<pair<int, int>> s; // commonly used for generating both FSR[] and FSL[] | |
// Populate FSR[] with the first smaller elements of the respective 'i'th building/height on the right side | |
vector<int> FSR(n); | |
int i = 0; | |
// Time & Space: O(N); | |
while(i < n) { | |
if(s.empty()) { | |
s.push(make_pair(heights[i], i)); | |
++i; | |
} else { | |
while((!s.empty()) && (s.top().first <= heights[i]) && (i < n)) { | |
s.push(make_pair(heights[i], i)); | |
++i; | |
} | |
if(i == n) break; | |
while((!s.empty()) && (s.top().first > heights[i])) { | |
FSR[s.top().second] = i; | |
s.pop(); | |
} | |
} | |
} | |
// The remaining elements in the stack don't have a smaller element in heights[] compared to themselves, | |
// so remove them from the stack, and mark FSR[] of that element as itself. | |
emptyTheStack(s, FSR, n); | |
// Populate FSR[] with the first smaller elements of the respective 'i'th building/height on the right side | |
vector<int> FSL(n); | |
i = n-1; | |
// Time & Space: O(N) | |
while(i >= 0) { | |
if(s.empty()) { | |
s.push(make_pair(heights[i], i)); | |
--i; | |
} else { | |
while((!s.empty()) && (s.top().first <= heights[i]) && (i >= 0)) { | |
s.push(make_pair(heights[i], i)); | |
--i; | |
} | |
if(i < 0) break; | |
while((!s.empty()) && (s.top().first > heights[i])) { | |
FSL[s.top().second] = i; | |
s.pop(); | |
} | |
} | |
} | |
// The remaining elements in the stack don't have a smaller element in heights[] compared to themselves, | |
// so remove them from the stack, and mark FSR[] of that element as itself. | |
emptyTheStack(s, FSL, -1); | |
int maxArea = -1; | |
for(int i = 0; i < n; ++i) { | |
// Since we're excluding one of the lines, the x-axis is subtracted by 2 | |
// Otherwise, we would subtract only 1, which is commented below in line #85. | |
maxArea = max(maxArea, heights[i] * (FSR[i] - FSL[i] - 2)); | |
// maxArea = max(maxArea, heights[i] * (FSR[i] - FSL[i] - 1)); | |
} | |
return maxArea; | |
} | |
// Time: O(2N); Space: O(N); | |
void replaceWaterWithBuildings(vector<int> &heights, const int n) { | |
// STEP 1: Find the Water on top of each building 'i' by finding the highest building on the left side of building | |
// 'i' and then finding the highest building on the right side of building 'i'. | |
vector<int> LM(n); // contains the heights of the highest building on the left side of building 'i' | |
LM[0] = heights[0]; | |
for(int i = 1; i < n; ++i) | |
LM[i] = max(LM[i-1], heights[i]); // Carrying forward the old height into the new one | |
int RM = INT_MIN; // contains the height of the highest building on the right side of building - 'i' | |
// STEP 1.1: Here, we are converting the original building heights into | |
// buildings of old height + water on top of them. | |
// Basically, converting the problem so that, there's no water on top of any building, | |
for(int i = n-1; i > -1; --i) { | |
RM = max(RM, heights[i]); | |
heights[i] = min(LM[i], RM); | |
} | |
} | |
// Asymptotic Time: O(N); Asymptotic Space: O(N); | |
int findMaxContainerArea(vector<int> &heights, const int n) { | |
replaceWaterWithBuildings(heights, n); | |
return findMaxRectangularArea(heights, n); | |
} | |
int main() { | |
int t; cin >> t; | |
while(t--) { | |
int n; cin >> n; | |
vector<int> heights(n); | |
for(int i = 0; i < n; ++i) | |
cin >> heights[i]; | |
cout << findMaxContainerArea(heights, n) << endl; | |
} | |
return 0; | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Problem Link
Test Link