Leetcode

Increasing Triplet Subsequence

  • Time:O(n)
  • Space:O(1)

C++

class Solution {
 public:
  bool increasingTriplet(vector<int>& nums) {
    int first = INT_MAX;
    int second = INT_MAX;

    for (const int num : nums)
      if (num <= first)
        first = num;
      else if (num <= second)  // first < num <= second
        second = num;
      else
        return true;  // first < second < num (third)

    return false;
  }
};

JAVA

class Solution {
  public boolean increasingTriplet(int[] nums) {
    int first = Integer.MAX_VALUE;
    int second = Integer.MAX_VALUE;

    for (final int num : nums)
      if (num <= first)
        first = num;
      else if (num <= second) // first < num <= second
        second = num;
      else // first < second < num (third)
        return true;

    return false;
  }
}

Python

class Solution:
  def increasingTriplet(self, nums: List[int]) -> bool:
    first = math.inf
    second = math.inf

    for num in nums:
      if num <= first:
        first = num
      elif num <= second:  # first < num <= second
        second = num
      else:
        return True  # first < second < num (third)

    return False