334. Increasing Triplet Subsequence (Medium)

https://leetcode.com/problems/increasing-triplet-subsequence/

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Input: [1,2,3,4,5]
Output: true

Input: [5,4,3,2,1]
Output: false

Solutions

1.

class Solution {

    // Firstly, Initialize the first and second element; Then, update the them if meets better alternatives;
    // 3. Finally, return true if hit element > second.

    public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length <= 2) {
            return false;
        }

        int len = nums.length;

        int first = nums[0];
        int second = nums[0];

        int i = 1;
        for (; i < len; i++) {
            if (nums[i] > first) {
                second = nums[i];
                break;
            }

            if (nums[i] < first) {
                first = nums[i];
            }
        }

        // second not found or second is the last one
        if (i >= len - 1) {
            return false;
        }

        // Now, we get the sort a ascending pair (one, second). But I need to point out that it doesn't
        // represent they will form the final answer.

        // Move on to find the third element.
        i++;

        for (; i < len; i++) {
            if (nums[i] > second) {
                return true;
            }

            // to reach here, subject to nums[i] <= second and nums[i-1] <= second

            // Here we have 3 jobs to do:

            // 1. replace second only
            if (nums[i] < second && nums[i] > first) {
                second = nums[i];
                continue;
            }

            // 2. replace one and second both, must cover = situation
            // [5,6,1,6,2,3], [5,6,2,3]
            if (nums[i - 1] <= first && nums[i] <= second && nums[i - 1] < nums[i]) {
                first = nums[i - 1];
                second = nums[i];
                continue;
            }

            // 3. ignore nums[i]

            // we cannot replace one with nums[i] because of the index sequence disorder issue
        }

        return false;
    }
}

2.

class Solution {

    // This problem is too trivial and nasty. A great number of special cases need to be covered.

    public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length <= 2) {
            return false;
        }

        int len = nums.length;

        int first = nums[0];
        int second = Integer.MAX_VALUE;

        int min = nums[0];

        for (int i = 1; i < len; i++) {

            // global minimum value
            min = Math.min(min, nums[i]);

            // if second is not assigned value yet
            // [4,1,2], [1,3,4]
            if (second == Integer.MAX_VALUE && nums[i] > nums[i - 1]) {
                first = nums[i - 1];
                second = nums[i];
                continue;
            }

            // if (i-1, i) is a ascending pair
            if (nums[i] > nums[i - 1]) {
                // [1,5,3], (1,3) is better than (1,5)
                if (nums[i - 1] > first && nums[i - 1] < second) {
                    second = nums[i - 1];
                }
                // min can be any values before i-1, so sequence min < nums[i - 1] < nums[i] meets
                // the requirement.
                else if (nums[i - 1] > min) {
                    return true;
                }
                // nums[i-1]<nums[i]<second, choose the minimums from both (first, nums[i-1])
                // and (second, nums[i]).
                else if (nums[i] < second) {
                    if (first < nums[i - 1]) {
                        second = nums[i - 1];
                    } else {
                        first = nums[i - 1];
                        second = nums[i];
                    }

                    // Following statements are incorrect. If first is set to nums[i-1], second
                    // must be nums[i]. Supposed second not change, index of second will be
                    // smaller than one.

                    // first = Math.min(first, nums[i - 1]);
                    // second = Math.min(second, nums[i]);
                }
            }

            // To narrow down the search scale, no need to take the descending pair into account.

            // one and second are already settled, if nums[i] > second, the ascending
            // sequence of length 3 is found.
            if (second != Integer.MAX_VALUE && nums[i] > second) {
                return true;
            }
        }

        return false;
    }
}

Incorrect Solutions

class Solution {

    // FIXME Incorrect Solution, extra space is not allowed.

    // Apply a stack, walk through nums elements and push into elements smaller than
    // the stack top, meanwhile pop out the larger value until current nums element can get in.
    // Return directly if desired ans found.

    public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length <= 2) {
            return false;
        }

        // failed case [2,3,1,4]

        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < nums.length; i++) {

            // FIXME stack.peek() == nums[i] will still be popped.

            while (!stack.isEmpty() && stack.peek() >= nums[i]) {
                stack.pop();
            }

            stack.push(nums[i]);

            if (stack.size() == 3) {
                return true;
            }
        }

        return false;
    }
}

References