Skip to content

334. Increasing Triplet Subsequence 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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