package com.fishercoder.solutions;

/**
 * 334. 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.
 * Your algorithm should run in O(n) time complexity and O(1) space complexity.

 Examples:
 Given [1, 2, 3, 4, 5],
 return true.

 Given [5, 4, 3, 2, 1],
 return false.
 */
public class _334 {

    public static class Solution1 {
        /**Time: O(n^2)
         * Space: O(1)*/
        public boolean increasingTriplet(int[] nums) {
            if (nums == null || nums.length == 0) {
                return false;
            }
            int small = nums[0];
            int medium = Integer.MAX_VALUE;
            for (int i = 1; i < nums.length; i++) {
                small = Math.min(small, nums[i - 1]);
                if (nums[i] > small) {
                    medium = Math.min(medium, nums[i]);
                    for (int j = i + 1; j < nums.length; j++) {
                        if (nums[j] > nums[i] || nums[j] > medium) {
                            return true;
                        }
                    }
                }
            }
            return false;
        }
    }

    public static class Solution2 {
        /**
         * Time: O(n)
         * Space: O(1)
         */
        public boolean increasingTriplet(int[] nums) {
            int small = Integer.MAX_VALUE;
            int big = Integer.MAX_VALUE;
            for (int num : nums) {
                if (num <= small) {
                    small = num;
                } else if (num <= big) {
                    big = num;
                } else {
                    return true;
                }
            }
            return false;
        }
    }

}

@@ -33,494 +33,8 @@
 s;%0A%0A
-/**%0A * 334. Increasing Triplet Subsequence%0A *%0A * Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.%0A *%0A * Formally the function should:%0A * Return true if there exists i, j, k%0A * such that arr%5Bi%5D %3C arr%5Bj%5D %3C arr%5Bk%5D given 0 %E2%89%A4 i %3C j %3C k %E2%89%A4 n-1 else return false.%0A * Your algorithm should run in O(n) time complexity and O(1) space complexity.%0A%0A Examples:%0A Given %5B1, 2, 3, 4, 5%5D,%0A return true.%0A%0A Given %5B5, 4, 3, 2, 1%5D,%0A return false.%0A */%0A
 publ
@@ -97,16 +97,28 @@
      /**
+%0A         * 
 Time: O(
@@ -144,16 +144,26 @@
 ce: O(1)
+%0A         
 */%0A     

refactor 334