Increasing Triplet Subsequence

Medium
208.

Increasing Triplet Subsequence

Increasing Triplet Subsequence is a medium coding problem on arrays and greedy, asked in Amazon, Google, Microsoft and Meta interviews.

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

Example 1

Input
nums = [1,2,3,4,5]
Output
true
Explanation
Any three increasing positions work.

Example 2

Input
nums = [5,4,3,2,1]
Output
false
Explanation
The array is strictly decreasing.

Example 3

Input
nums = [2,1,5,0,4,6]
Output
true
Explanation
0 < 4 < 6 at indices 3, 4, 5.

Constraints

  • 1 <= nums.length <= 40
  • -1000 <= nums[i] <= 1000

Follow-up: Can you do it in O(n) time and O(1) space?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var increasingTriplet = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Increasing Triplet Subsequence — Problem & Solution

Increasing Triplet Subsequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Increasing Triplet Subsequence is a medium coding problem on arrays and greedy, asked in Amazon, Google, Microsoft and Meta interviews.

  • Difficulty: Medium
  • Topics: Arrays, Greedy
  • Asked at: Amazon, Google, Microsoft, Meta, Nutanix
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

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

Example 1

Input: nums = [1,2,3,4,5]
Output: true
Explanation: Any three increasing positions work.

Example 2

Input: nums = [5,4,3,2,1]
Output: false
Explanation: The array is strictly decreasing.

Example 3

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: 0 < 4 < 6 at indices 3, 4, 5.

Constraints

  • 1 <= nums.length <= 40
  • -1000 <= nums[i] <= 1000

Follow-up: Can you do it in O(n) time and O(1) space?

Hints for Increasing Triplet Subsequence

  1. Hint 1

    Keep the smallest value seen so far, and the smallest value that already has something smaller before it.

  2. Hint 2

    Anything strictly greater than that second value completes a triple.

  3. Hint 3

    Lowering first after second is set is safe — second still records that a valid pair existed earlier.

How to solve Increasing Triplet Subsequence

Track first, the smallest value so far, and second, the smallest value that already has something smaller before it. Any element larger than second completes a triple.

Approach

  1. Initialise first = second = +∞.
  2. For each x: if x <= first, set first = x; else if x <= second, set second = x; else return true.
  3. Return false.

Why it works

second is only ever set when a smaller first preceded it, so an x > second has two smaller predecessors in order. Lowering first afterwards is safe: second still records that a valid pair existed earlier.

Complexity

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

Pitfalls

  • Using strict < instead of <= lets equal values slip through as an "increase".
  • The final first may sit to the right of second — that does not invalidate the answer.

Reference solution

Python

def increasingTriplet(nums) -> bool:
    first = second = float("inf")
    for x in nums:
        if x <= first:
            first = x
        elif x <= second:
            second = x
        else:
            return True
    return False

Java

public static boolean increasingTriplet(int[] nums) {
    long first = Long.MAX_VALUE, second = Long.MAX_VALUE;
    for (int x : nums) {
        if (x <= first) first = x;
        else if (x <= second) second = x;
        else return true;
    }
    return false;
}

C++

bool increasingTriplet(vector<int>& nums) {
    long long first = 4000000000LL, second = 4000000000LL;
    for (int x : nums) {
        if (x <= first) first = x;
        else if (x <= second) second = x;
        else return true;
    }
    return false;
}

JavaScript

var increasingTriplet = function(nums) {
    let first = Infinity, second = Infinity;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] <= first) first = nums[i];
        else if (nums[i] <= second) second = nums[i];
        else return true;
    }
    return false;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms