Question

Cisco | OA Coding Questions and Solutions | Set - 9 | 2022

Answer 1

Can anyone please solve this?

Answer 2

#include<bits/stdc++.h>
using namespace std;

int largestSquareSide(vector<int>& a) {
    int n = a.size();
    stack<int>st; 
    vector<int>left(n,0), right(n,0);
    for(int i=0;i<n;i++){
        while(st.size() && a[st.top()]>=a[i]){
            st.pop();
        }
        if(st.size()){
            left[i] = st.top();
        }else{
            left[i] = -1;
        }
        st.push(i);
    }
    while(st.size()){st.pop();}
    for(int i=n-1;i>=0;i--){
        while(st.size() && a[st.top()]>=a[i]){
            st.pop();
        }
        if(st.size()){
            right[i] = st.top();
        }else{
            right[i] = n;
        }
        st.push(i);
    }
    while(st.size()){st.pop();}
    int ans = 0;
    for(int i=0;i<n;i++){
        int mini = min(a[i] , right[i]-left[i]-1);
        ans = max(ans,mini);
    }
    return ans;
}

signed  main(){
	int n;
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    cout<<largestSquareSide(a)<<endl;
    return 0;
}

 

monotonic stack will work
similar to https://leetcode.com/problems/container-with-most-water/