nikunjsoni

975

Apr 3rd, 2021
77
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int oddEvenJumps(vector<int>& arr) {
  4.         // Sort the array in ascending order.
  5.         vector< pair<int, int> > narr;
  6.         for(int i=0; i<arr.size(); i++)
  7.             narr.push_back({arr[i], i});
  8.         sort(narr.begin(), narr.end());
  9.        
  10.         // Find next higher using monotonic stack.
  11.         vector<int> s;
  12.         vector<int> next_higher(arr.size(), -1);
  13.         for(auto p: narr){
  14.             while(!s.empty() && s.back() < p.second){
  15.                 next_higher[s.back()] = p.second;
  16.                 s.pop_back();
  17.             }
  18.             s.push_back(p.second);
  19.         }
  20.        
  21.         // Sort in descending order.
  22.         narr.clear();
  23.         for(int i=0; i<arr.size(); i++)
  24.             narr.push_back({-arr[i], i});
  25.         sort(narr.begin(), narr.end());
  26.        
  27.         // Find next lower using monotonic stack.
  28.         s.clear();
  29.         vector<int> next_lower(arr.size(), -1);
  30.         for(auto p: narr){
  31.             while(!s.empty() && s.back() < p.second){
  32.                 next_lower[s.back()] = p.second;
  33.                 s.pop_back();
  34.             }
  35.             s.push_back(p.second);
  36.         }
  37.        
  38.         // Use boolean dp to store if we can jump upto last index.
  39.         int sz = arr.size();
  40.         bool dp[sz][2];
  41.         memset(dp, 0, sizeof(dp));
  42.         dp[sz-1][0] = true;
  43.         dp[sz-1][1] = true;
  44.        
  45.         for(int i=sz-2; i>=0; i--){
  46.             if(next_higher[i] != -1)
  47.                 dp[i][0] = dp[next_higher[i]][1];
  48.             if(next_lower[i] != -1)
  49.                 dp[i][1] = dp[next_lower[i]][0];
  50.         }
  51.         int ans = 0;
  52.         for(int i=0; i<sz; i++){
  53.             if(dp[i][0]) ans++;
  54.         }
  55.         return ans;
  56.     }
  57. };
RAW Paste Data