Area of Container with the Most Amount of Water [TC: O(N); SC: O(N)]

area-container-max.cpp

// 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;
}

Problem Link
Test Link