Share my easy and simple solution


  • 8

    Idea: Find peak and bottom

    For every [bottom, peak], find if there is one number bottom<number<peak.

    public class Solution {
        public boolean find132pattern(int[] nums) {
            if(nums.length<3) return false;
            Integer low = null, high = null;
            int start = 0, end = 0;
            while(start<nums.length-1){
                while(start<nums.length-1 && nums[start]>=nums[start+1]) start++;
                // start is lowest now
                int m = start+1;
                while(m<nums.length-1 && nums[m]<=nums[m+1]) m++;
                // m is highest now
                int j = m+1;
                while(j<nums.length){
                    if(nums[j]>nums[start] && nums[j]<nums[m]) return true;
                    j++;
                }
                start = m+1;
            }
            return false;
        }
    }
    

  • 1
    L

    Thanks for sharing and the worst case time complexity for this one is O(n^2) when the array is in ascending order, right?


  • 0
    L

    This is great and neat!


  • 0
    D

    Same idea, but only beats 8.23% of java submissions.

    public boolean find132pattern(int[] nums) {
        int cur = 0;
        int size = nums.length;
        while(cur < size - 2) {
            int val = nums[cur];
            int i = cur;
            while(i + 1 < size && nums[i] > nums[i+1]) i++;
            int j = i + 1;
            while(j + 1 < size && nums[j] < nums[j+1]) j++;
            for (int k = j + 1 ; k < size ; k++) {
                if (nums[i] < nums[k] && nums[k] < nums[j]) {
                    return true;
                }
            }
            cur++;
        }
        return false;
    }

  • 0
    C

    nice and easy to follow!


  • 2
    T

    Does this solution pass as a python implementation? I tried implementing the same code in python but it gives me time limit exceeded.


  • 0
    T

    whats the complexity of this sol ?O(N) ?


Log in to reply
 

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