108: Increasing triplet subsequence

Given an array of integers, check if exists a subsequence of length three where array[i] < array[j] < array[k] and i < j < k

Note: Try to solve for O(n) time complexity

 

Example 1

Input:   [1, 0, 3, 5]

Output:  true

Explanation: [1, 3, 5] or [0, 3, 5]

Example 2

Input:   [5, 6, 4, 3]

Output:  false