A general Java solution


  • 0
    J

    You can change three to whatever number k, time complexity is O(NlgK), in this case, k is constant, thus O(N).

    class Solution {
        public boolean increasingTriplet(int[] nums) {
            int[] three = new int[3];
            int p = -1;
            for (int n: nums) {
                int idx = Arrays.binarySearch(three, 0, p + 1, n);
                if (idx < 0) idx = -idx - 1;
                if (idx == 2) return true;
                three[idx] = n;
                if (p < idx) p = idx;
            }
            return false;
        }
    }
    

Log in to reply
 

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