Concise Java O(n^2) Solution


  • 0
    Y

    O(n^3) solution is naive, O(n) solution is challenging. This is the O(n^2) solution.

    public boolean find132pattern(int[] nums) {
            if (nums.length < 3)
                return false;
    
            for (int i = 0; i < nums.length; i++) {
                //min/max are min value/max value in 132 pattern.
                int min = nums[i], max = Integer.MIN_VALUE;
    
                //min cannot be changed in for loop below.
                for (int j = i + 1; j < nums.length; j++) {
                    if (nums[j] > min && nums[j] > max) {
                        max = nums[j];
                    } else if (nums[j] < max && nums[j] > min) {
                        return true;
                    }
                }
            }
    
            return false;
        }
    

Log in to reply
 

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