[LeetCode] 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.

Thought process:

Iterate through the array. Use two variables to keep track of the smallest and the middle number. There are three cases:

1. Current number <= smallest number: update smallest.
2. Smallest < current number <= middle number: update middle.
3. Current number > middle number: there is an increasing sub-sequence of length 3.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

public class Solution { public boolean increasingTriplet(int[] nums) { int first = Integer.MAX_VALUE; int second = Integer.MAX_VALUE; for (int num : nums) { if (num <= first) { first = num; } else if (num <= second) { second = num; } else { return true; } } return false; } }

Time complexity: O(n).