Welcome to Subscribe On Youtube

334. Increasing Triplet Subsequence

Description

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

 

Example 1:

Input: nums = [1,2,3,4,5]
Output: true
Explanation: Any triplet where i < j < k is valid.

Example 2:

Input: nums = [5,4,3,2,1]
Output: false
Explanation: No triplet exists.

Example 3:

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

 

Constraints:

• 1 <= nums.length <= 5 * 105
• -231 <= nums[i] <= 231 - 1

 

Follow up: Could you implement a solution that runs in O(n) time complexity and O(1) space complexity?

Solutions

O(n) time complexity and O(1) space complexity

The idea is to use two pointers m1 and m2, initialized to the integer maximum value, we traverse the array, if m1 is greater than or equal to the current number, the current number is assigned to m1; if m1 is less than the current number and m2 is greater than or equal to the current number, then The current number is assigned to m2.

Once m2 is updated, it means that there must be a number less than m2, then we have successfully formed an increasing subsequence of length 2, so once we traverse to a number larger than m2, we directly return true.

If we encounter a number smaller than m1, we still need to update m1. If possible, we must also update m2 to a smaller value. After all, the smaller the value of m2, the greater the possibility of forming an increasing sequence of length 3.

Cache range max/min

The idea of this solution is to create two arrays, forward array and backward array,

• forward[i] represents the smallest number between [0, i],
• backward[i] represents the largest number between [i, n-1].

Then for any position i, if forward[i] <nums[i] <backward[i] is satisfied, it means that this incremental ternary subsequence exists

Let’s take an example, such as:

nums: 8 3 5 1 6

foward: 8 3 3 1 1

backward: 8 6 6 6 6

We find that the number 5 satisfies forward[i] <nums[i] <backward[i], so the ternary subsequence exists.

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

• class Solution {
      public boolean increasingTriplet(int[] nums) {
          int min = Integer.MAX_VALUE, mid = Integer.MAX_VALUE;
          for (int num : nums) {
              if (num > mid) {
                  return true;
              }
              if (num <= min) {
                  min = num;
              } else {
                  mid = num;
              }
          }
          return false;
      }
  }
  

• class Solution {
  public:
      bool increasingTriplet(vector<int>& nums) {
          int mi = INT_MAX, mid = INT_MAX;
          for (int num : nums) {
              if (num > mid) return true;
              if (num <= mi)
                  mi = num;
              else
                  mid = num;
          }
          return false;
      }
  };
  

• class Solution(object):
    def increasingTriplet(self, nums):
      """
      :type nums: List[int]
      :rtype: bool
      """
      a = b = float("inf")
      for num in nums:
        if num <= a:
          a = num
        elif num <= b:
          b = num
        else:
          return True
      return False
  
  ################
  
  class Solution: # dp
      def increasingTriplet(self, nums: List[int]) -> bool:
          if not nums or len(nums) < 3:
              return False
  
          forward = [nums[0]]
          for num in nums[1:]:
              forward.append(min(forward[-1], num))
  
          backward = [nums[-1]]
          for num in nums[-2::-1]:
              # costly op for insert() for runnig time
              backward.insert(0, max(backward[0], num))
          return any(forward[i] < nums[i] < backward[i] for i in range(len(nums)))
  
  
  ############
  
  class Solution:
      def increasingTriplet(self, nums: List[int]) -> bool:
          mi, mid = inf, inf
          for num in nums:
              if num > mid:
                  return True
              if num <= mi:
                  mi = num
              else:
                  mid = num
          return False
  
  

• func increasingTriplet(nums []int) bool {
  	min, mid := math.MaxInt32, math.MaxInt32
  	for _, num := range nums {
  		if num > mid {
  			return true
  		}
  		if num <= min {
  			min = num
  		} else {
  			mid = num
  		}
  	}
  	return false
  }
  

• function increasingTriplet(nums: number[]): boolean {
      let n = nums.length;
      if (n < 3) return false;
      let min = nums[0],
          mid = Number.MAX_SAFE_INTEGER;
      for (let num of nums) {
          if (num <= min) {
              min = num;
          } else if (num <= mid) {
              mid = num;
          } else if (num > mid) {
              return true;
          }
      }
      return false;
  }
  
  

• impl Solution {
      pub fn increasing_triplet(nums: Vec<i32>) -> bool {
          let n = nums.len();
          if n < 3 {
              return false;
          }
          let mut min = i32::MAX;
          let mut mid = i32::MAX;
          for num in nums.into_iter() {
              if num <= min {
                  min = num;
              } else if num <= mid {
                  mid = num;
              } else {
                  return true;
              }
          }
          false
      }
  }
  
  

All Problems

All Solutions