Stack

  1. We need to process the array from right to left
  2. Using stack we end up processing each element just 2 times , hence the complexity is just O(n)
void nextgreaterelement(){vector<int>v;stack<int>st;v.push_back(2);v.push_back(1);v.push_back(2);v.push_back(4);v.push_back(3);vector<int>result;result.resize(v.size(),-1);for(int i=v.size()-1;i>=0;i--){    while(!st.empty()&&st.top()<=v[i])   {      st.pop();     }     if(!st.empty())     result[i]=st.top();     st.push(v[i]);}for(int i=0;i<result.size();i++)cout<<result[i]<<" ";}
  1. https://leetcode.com/problems/car-fleet-ii/discuss/1086364/Full-detailed-explaination-starting-with-a-simplier-problem

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store