Increasing Triplet Subsequence

Problem Statement

You are given an integer array nums. You need to determine if there exists a triplet of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k].

Return true if such a triplet exists, otherwise return false.

Examples

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

Example 3:

Input: nums = [2, 1, 5, 0, 4, 6]
Output: true

Explanation: The triplet (3, 4, 5) is valid because num[3] == 0 < nums[4] == 4 < nums[5] == 6

Different Approaches

1️⃣ Two Pointers with Greedy Strategy

Intuition:

We want to find three increasing elements that appear in sequence. The goal is to use two pointers (first, second) to keep track of the smallest and the middle values of a potential triplet as we iterate through the array.

1. first keeps track of the smallest value we've encountered so far.
2. second keeps track of the next smallest value that's greater than first but smaller than any larger number that could be a part of the triplet.
3. As we iterate through the array, if we find a number larger than both first and second, we know a valid triplet exists.

Approach:

1. Initialize two variables first and second to hold the smallest and middle values respectively. Set them to very large values (infinity).
2. Iterate through the array:
   • If the current element is smaller than first, update first.
   • If the current element is larger than first but smaller than second, update second.
   • If the current element is larger than both first and second, return true (since an increasing triplet exists).
3. If no valid triplet is found after the loop, return false.

Dry Run:

Initialization:

       +-----+-----+-----+-----+-----+-----+
nums = |  2  |  1  |  5  |  0  |  4  |  6  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5

first = INT_MAX
second = INT_MAX

First Iteration:

       +-----+-----+-----+-----+-----+-----+
nums = |  2  |  1  |  5  |  0  |  4  |  6  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
          ^
          |
          i

first = INT_MAX
second = INT_MAX

num[i] = 2
  since nums[i] <= first
              2 <= INT_MAX
              update first = 2

Second Iteration:

       +-----+-----+-----+-----+-----+-----+
nums = |  2  |  1  |  5  |  0  |  4  |  6  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                ^
                |
                i

first = 2
second = INT_MAX

num[i] = 1
  since nums[i] <= first
              1 <= 2
              update first = 2

Third Iteration:

       +-----+-----+-----+-----+-----+-----+
nums = |  2  |  1  |  5  |  0  |  4  |  6  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                      ^
                      |
                      i

first = 1
second = INT_MAX

  num[i] = 5
  since nums[i] > first
              5 > 2
  and nums[i] <= second
            5 <= INT_MAX
            update second = 5

Fourth Iteration:

       +-----+-----+-----+-----+-----+-----+
nums = |  2  |  1  |  5  |  0  |  4  |  6  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                            ^
                            |
                            i

first = 1
second = 5

  num[i] = 0
  since nums[i] <= first
              0 <= 1
              update first = 0

Fifth Iteration:

       +-----+-----+-----+-----+-----+-----+
nums = |  2  |  1  |  5  |  0  |  4  |  6  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                                  ^
                                  |
                                  i

first = 0
second = 5

  num[i] = 4
  since nums[i] > first
              4 > 0
  and nums[i] <= second
            4 <= 5
            update second = 4

Sixth Iteration:

       +-----+-----+-----+-----+-----+-----+
nums = |  2  |  1  |  5  |  0  |  4  |  6  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                                        ^
                                        |
                                        i

first = 0
second = 4

  num[i] = 6
  since nums[i] > first
              6 > 0
  and nums[i] > second
            6 > 4
This means you have found an increasing template:
first = 0
second = 4
current = 6
We immediately return true.

Different Approaches

1️⃣ Two Pointers with Greedy Strategy

Intuition:

We want to find three increasing elements that appear in sequence. The goal is to use two pointers (first, second) to keep track of the smallest and the middle values of a potential triplet as we iterate through the array.

1. first keeps track of the smallest value we've encountered so far.
2. second keeps track of the next smallest value that's greater than first but smaller than any larger number that could be a part of the triplet.
3. As we iterate through the array, if we find a number larger than both first and second, we know a valid triplet exists.

Approach:

1. Initialize two variables first and second to hold the smallest and middle values respectively. Set them to very large values (infinity).
2. Iterate through the array:
   • If the current element is smaller than first, update first.
   • If the current element is larger than first but smaller than second, update second.
   • If the current element is larger than both first and second, return true (since an increasing triplet exists).
3. If no valid triplet is found after the loop, return false.

Code:

#include <vector>
#include <limits.h>
using namespace std;

bool increasingTriplet(vector<int>& nums) {
    int first = INT_MAX;
    int second = INT_MAX;

    for (int num : nums) {
        if (num <= first) {
            // Update first (smallest number)
            first = num;
        } else if (num <= second) {
            // Update second (middle number)
            second = num;
        } else {
            // If we find a number greater than both first and second, we found the triplet
            return true;
        }
    }

    return false; // No triplet found
}

Complexity Analysis:

• Time Complexity: O(n), where n is the number of elements in the array.
  • The algorithm consists of a single pass through the input array, iterating over each element exactly once. Each iteration involves basic operations such as comparisons and assignments, which take constant time.
• Space Complexity: O(1)
  • We are using only two extra variables (first and second) to store the smallest and middle values. No additional data structures (such as arrays or hash maps) are being used, which makes the space complexity as constant.