Leetcode 334 – Increasing Triplet Subsequence

Problem link

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

Suppose the elements that form the answer are a,b,c. The smallest element you ever encounter will be a. So if you see [1,-2,4,5], you first assign a to -1. Then look at -2. It can’t be the b, so update a to be -2. This is ok because if \(a_{new} < a_{old}\) then any increasing subsequence that began with \(a_{old}\) will still be an increasing subsequence after replacing \(a_{old}\) with \(a_{new}\) as \(a_{new} \lt a_{old}\).

The following piece of code solves the problem:

public boolean increasingTriplet(int[] nums) {
  int a,b,c;
  a = b = c = Integer.MAX_VALUE;

  for(int n : nums) {
    a = Math.min(a,n);
    if (a == n) continue;
    b = Math.min(b,n);
    if (b == n) continue;
    c = Math.min(c,n);
  }
  return (a < b) && (b < c) && 
    (a != Integer.MAX_VALUE && b != Integer.MAX_VALUE && c != Integer.MAX_VALUE);
}