Java 3ms with binary search, O(n) time and O(k) space


  • 0
    Y
    public boolean increasingTriplet(int[] nums) {
        // using an array, minForLen,
        // minForLen[l] represents the smallest number for increasing subsequence of length l 
        // for each number nums[i], do binary search in minForLen
        // for the index l that corresponds to the largest number smaller than nums[i],
        // and the longest increasing sebsequence up to and including nums[i] will be of length l + 1, return true if it is >= 3
        if (nums == null) {
            return false;
        }
        int[] minForLen = new int[3]; // since we only need to decide existence of inceasing subsequence of length 3
        Arrays.fill(minForLen, Integer.MAX_VALUE);
        minForLen[0] = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int indLargestSmaller = largestSmaller(minForLen, nums[i]);
            if (indLargestSmaller == 2) {
                return true;
            }
            minForLen[indLargestSmaller + 1] = Math.min(minForLen[indLargestSmaller + 1], nums[i]);
        }
        return false;
    }
    
    private int largestSmaller(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right - 1) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return nums[right] < target ? right : nums[left] < target ? left : -1;
    }

Log in to reply
 

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