Java O(nlogn) time and O(1) space solution(11ms) with detailed explanation


  • 0

    This solution is quite intuitive. It is inspired by jade86's solution. Thanks a lot!
    Since we want to find the three elements where ai < ak < aj and i < j < k, we can find the valid ak in the array first and then find the valid ai which is smaller than ak. We can search the array from right to left with one pass. I'll explan it with the following example.
    Input: [1, 2, 3, 4, 1, 2, 4, 1]
    Output: True
    Explanation:
    We always find ak in part of array which consist of a large enough element followed by ascending order sequence. I use low to record the first element value in the ascending sequence and left as position while use high to record the last element value and right as position in my code.
    First time we search the colored part and get aj = 4, ak = 1. left = 7, right = 7.
    [1, 2, 3, 4, 1, 2, 4, 1]
    Second time we search the colored part and get aj = 4, ak = 2. Since this akis larger than last one, we update ak. We can use binary search to find ak with O(logn) time complexity. left = 4, right = 6.
    [1, 2, 3, 4, 1, 2, 4, 1]
    Second time we search the colored part and we can find valid ai where ai < ak.
    [1, 2, 3, 4, 1, 2, 4, 1]
    The overall time complexity is O(nlogn) while the space complexity is O(1). Without stack this solution is quite fast and beats 98% solutions.

    public class Solution {
        public boolean find132pattern(int[] nums) {
            if (nums.length < 3) return false;
            int aj = Integer.MIN_VALUE, ak = Integer.MIN_VALUE;
            int high = nums[nums.length-1], low = nums[nums.length-1];
            int left = nums.length-1, right = nums.length-1;
            for (int i=nums.length-2; i>=0; i--) {
                if (nums[i] < ak) return true;
                else if (nums[i] <= low) {
                    low = nums[i];
                    left = i;
                } else if (nums[i] > low) {
                    if (nums[i] <= high) {
                        while (left<=right) {
                            int mid = left+(right-left)/2;
                            if (nums[mid]<nums[i] && nums[mid+1]>=nums[i]) {
                                if (nums[mid] > ak) {
                                    ak = nums[mid];
                                    aj = nums[i];
                                }
                                break;
                            } else if (nums[mid]<nums[i]) left = mid+1;
                            else right = mid-1;
                        }
                    } else {
                        if (high > ak) {
                            aj = nums[i];
                            ak = high;
                        }
                    }
                    low = high = nums[i];
                    left = right = i;
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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