334. Increasing Triplet Subsequence


Problem Description

The problem gives us an array of integers, nums, and asks us to determine if it is possible to find a sequence of three elements, where each element comes after the previous one in the order they appear in the array (i.e., they have increasing indices), and each element is greater than the one before it in this sequence. This sequence should satisfy the condition nums[i] < nums[j] < nums[k], where i, j, and k are the indices of these elements in the array, such that i < j < k. If such a sequence exists in nums, the function should return true, otherwise, it should return false.

This can be visualized as checking if there's an ascending subsequence of at least three numbers within the original array. It's essentially a question about identifying a pattern within a sequence without reordering it or changing the values.

Intuition

To arrive at the solution efficiently, instead of looking for the whole triplet right away, we can keep track of the smallest number we have encountered so far (mi) and a middle number that is greater than mi but smaller than any potential third number (mid). As we iterate through the array, we can update these two numbers whenever possible. The idea here is to maintain the lowest possible values for mi and mid as we move forward, giving us the best chance to find a number that would be greater than both, thus forming our triplet.

  • If the current number (num) is less than or equal to mi, it becomes the new mi because we're always interested in the smallest starting point of the potential triplet.
  • If num is greater than mi but less than mid, we have found a possible middle part of our triplet, so we set mid to this new number.
  • If num is greater than mid, this means we have successfully found a triplet (because num is greater than both mi and mid, which also implies that mi is less than mid), and we can return true.

This efficient approach uses a greedy-like method to continuously look for the most optimal mi and mid with the hope of finding a third number that could fit the sequence. It does so using a linear scan and constant extra space, without the need for sorting or extra arrays.

Learn more about Greedy patterns.

Solution Approach

The Reference Solution Approach begins with the creation of two variables: mi and mid, both initialized to inf (infinity). Here's the reasoning for each line of code:

  • mi and mid serve as placeholders to store the smallest and middle elements of the potential increasing triplet subsequence. By initializing them to infinity, it ensures that any number in the array will be smaller, allowing for proper updating of these variables.

The main algorithm unfolds within a single pass through the array of numbers (nums):

  • A for loop iterates through the nums array.
  • For each num in nums, there is a series of checks and updates:
    • if num > mid: This is the condition that tells us we have found a valid triplet. If the current num is greater than our mid value, then we already have a mi which is less than mid, and hence, we have found a sequence where mi < mid < num. We return True immediately.
    • if num <= mi: If the current num is smaller than or equal to the current smallest value mi, it means that we can potentially start a new triplet sequence with this num as the smallest element, thus we update mi with the value of num.
    • else: If the current num is greater than mi and not greater than mid, it fits between the mi and mid, so we update the mid to be num since it could potentially be the middle element of a valid triplet.

As the for loop continues, mi and mid are updated accordingly until either a valid triplet is found—causing the function to return True—or the algorithm completes the array iteration without finding a triplet, resulting in a return value of False.

It's important to note that the code uses a greedy approach to always maintain the smallest possible values for mi and mid as it iterates over nums. By consistently updating these with the smallest possible values at each step, it optimizes the chance of finding a valid triplet later in the array. No additional data structures are necessary, making this solution notably efficient with O(n) time complexity (due to single iteration through the array) and O(1) space complexity (using only two extra variables).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Example Walkthrough

Let's illustrate the solution approach using a small example where our input nums array is [1, 2, 3, 4, 5].

  • We initialize mi and mid to infinity. Current state: mi = inf, mid = inf.
  • We iterate over the array:
    • We compare the first element, 1, with mid. Since 1 < inf, we cannot form a triplet yet, but 1 becomes our new mi. Updated state: mi = 1, mid = inf.
    • We move to the next element, 2. Now, 2 is greater than mi but still less than mid. So, 2 becomes our new mid. Updated state: mi = 1, mid = 2.
    • Next element is 3. It is greater than both mi and mid. We now have a valid triplet: 1 < 2 < 3. Hence, according to our solution approach, we return True. There is no need to check the remaining elements (4 and 5) because we have successfully found an increasing triplet.

In this example, the approach quickly identifies the increasing sequence with the satisfaction of the conditions outlined in the problem description. The algorithm efficiently updates mi and mid and only stops when it confirms the existence of the increasing triplet.

Solution Implementation

1class Solution:
2    def increasingTriplet(self, nums: List[int]) -> bool:
3        # Initialize two variables with infinity which will
4        # represent the smallest and middle numbers of the triplet.
5        smallest = float('inf')
6        middle = float('inf')
7
8        # Iterate over the list of numbers.
9        for num in nums:
10            # If current number is greater than the middle number,
11            # an increasing triplet exists.
12            if num > middle:
13                return True
14          
15            # If current number is less than or equal to the smallest,
16            # update the smallest number to be the current number.
17            if num <= smallest:
18                smallest = num
19            # Otherwise, if the current number is between the smallest
20            # and the middle, update the middle number.
21            else:
22                middle = num
23
24        # Return False if no increasing triplet is found.
25        return False
26
1class Solution {
2
3    // Method to check if there exists an increasing triplet in the array.
4    public boolean increasingTriplet(int[] nums) {
5        // Initialize two variables to hold the smallest and the middle value found so far.
6        int smallest = Integer.MAX_VALUE;
7        int middle = Integer.MAX_VALUE;
8
9        // Iterate over each number in the array.
10        for (int num : nums) {
11            // If the current number is greater than the middle value found,
12            // an increasing triplet sequence exists.
13            if (num > middle) {
14                return true;
15            }
16
17            // If the current number is the smallest we've seen so far,
18            // we update the smallest value.
19            if (num <= smallest) {
20                smallest = num;
21            } else {
22                // Otherwise, if it's between the smallest and the middle value,
23                // we update the middle value.
24                middle = num;
25            }
26        }
27
28        // If we did not return true within the loop, then no increasing
29        // triplet sequence was found.
30        return false;
31    }
32}
33
1#include <vector>
2#include <climits> // Include for INT_MAX
3
4class Solution {
5public:
6    // This function checks if there exists an increasing triplet subsequence
7    // The sequence is increasing if nums[i] < nums[j] < nums[k] where i < j < k
8    // Parameters:
9    //     nums - a vector of integers
10    bool increasingTriplet(std::vector<int>& nums) {
11        int firstMin = INT_MAX; // Store the smallest number encountered
12        int secondMin = INT_MAX; // Store the second smallest number encountered
13
14        // Iterate over the input vector
15        for (int num : nums) {
16            // If we find a number greater than second smallest,
17            // this means we found a triplet; return true
18            if (num > secondMin) {
19                return true; 
20            }
21
22            // If current number is less than or equal to firstMin,
23            // update firstMin to the current number
24            if (num <= firstMin) {
25                firstMin = num; 
26            } else {
27                // If current number is between firstMin and secondMin
28                // update secondMin to the current number
29                // This is because we want the smallest possible value for secondMin
30                // that is greater than firstMin
31                secondMin = num; 
32            }
33        }
34
35        // If we have reached this point, it means we did not find
36        // an increasing triplet subsequence
37        return false;
38    }
39};
40
1/**
2 * Checks whether there exists an increasing triplet subsequence within the array
3 * @param nums - Array of numbers to check for the increasing triplet
4 * @returns boolean - True if there is an increasing triplet, False otherwise
5 */
6function increasingTriplet(nums: number[]): boolean {
7    let length = nums.length;
8
9    // If the array has fewer than 3 items, it can't have an increasing triplet
10    if (length < 3) return false;
11
12    // Initialize the smallest and middle values in the triplet
13    let smallest = nums[0];
14    let middle = Number.MAX_SAFE_INTEGER;
15
16    // Iterate through the array to find the increasing triplet
17    for (let number of nums) {
18        if (number <= smallest) {
19            // Current number becomes the new smallest if it's smaller or equal to the current smallest
20            smallest = number;
21        } else if (number <= middle) {
22            // Current number is greater than smallest but smaller or equal to middle,
23            // so it becomes the new middle
24            middle = number;
25        } else {
26            // If we found a number greater than both smallest and middle, we found an increasing triplet
27            return true;
28        }
29    }
30
31    // If no increasing triplet is found, return false
32    return false;
33}
34

Time and Space Complexity

The time complexity of the given code is O(n) where n is the number of elements in the nums list. This is because the code iterates through the entire nums list once with a single loop, and within each iteration, it performs a constant number of operations.

The space complexity of the given code is O(1) regardless of the size of the input list. It uses only two extra variables, mi and mid, which consume a constant amount of space.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following array represent a max heap?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄