O(n^2) 5-line C++ TLE solution (not fast, just for reference)


  • 0

    This is a short but O(N2) time and O(N) space TLE solution, so probably not what you want. The idea is to simply record each interval (mink<i numsk, numsi) and check whether current value numsi is in any previous such intervals.

        bool find132pattern(vector<int>& nums) {
          vector<pair<int, int>> intervals; int curMin = INT_MAX; 
          for (int x:nums) {
            for (auto& i : intervals) if (i.first < x && x < i.second) return true;
            intervals.emplace_back(curMin = min(curMin, x), x);
          }
          return false;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.