Question

Formatted question description: https://leetcode.ca/all/334.html

 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.

 Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

 Example 1:

 Input: [1,2,3,4,5]
 Output: true


 Example 2:

 Input: [5,4,3,2,1]
 Output: false

 @tag-array

Algorithm

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.

Code

Java

  • 
    public class Increasing_Triplet_Subsequence {
    
    
        class Solution {
            public boolean increasingTriplet(int[] nums) {
    
                if (nums == null || nums.length < 3) {
                    return false;
                }
    
                int first = Integer.MAX_VALUE;
                int second = Integer.MAX_VALUE;
    
                for (int i = 0; i < nums.length; i++) {
                    if (nums[i] <= first) {
                        first = nums[i];
                    // @note: must be <=
                    // more tests: [1,2,2,1], [1,1,2,2]
    
                    // @note: also work below line
                    // } else if (first <= nums[i] && nums[i] <= second) {
                    } else if (nums[i] <= second) {
                        second = nums[i];
                    } else {
                        return true;
                    }
                }
    
                return false;
            }
        }
    
    
        class SolutionCache {
            public boolean increasingTriplet(int[] nums) {
    
                if (nums == null || nums.length < 3) {
                    return false;
                }
    
                int[] forward = new int[nums.length];
                int[] backward = new int[nums.length];
    
                forward[0] = nums[0];
                for (int i = 1; i < nums.length; i++) {
                    forward[i] = Math.min(forward[i - 1], nums[i]);
                }
    
                backward[nums.length - 1] = nums[nums.length - 1];
                for (int i = nums.length - 2; i >= 0; i--) {
                    backward[i] = Math.max(backward[i + 1], nums[i]);
                }
    
                for (int i = 0; i < nums.length; i++) {
                    if (forward[i] < nums[i] && nums[i] < backward[i]) {
                        return true;
                    }
                }
    
                return false;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/increasing-triplet-subsequence/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        bool increasingTriplet(vector<int>& A) {
            int first = INT_MAX, second = INT_MAX;
            for (int n : A) {
                if (n <= first) first = n;
                else if (n <= second) second = n;
                else return true;
            }
            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
    
    

All Problems

All Solutions