Increasing Triplet Subsequence

Description

An increasing triplet subsequence in an array is a subsequence of three elements arr[i], arr[j], arr[k] such that i < j < k and arr[i] < arr[j] < arr[k].

In other words, it is a subset of three numbers in increasing order within the larger array.

For example, in [1, 2, 1, 5, 3, 4], [1, 3, 4] forms an increasing triplet subsequence.

Key properties:

The three indices must be unique.
The three elements must be in strictly increasing order.
Multiple increasing triplets can exist in an array.

Finding increasing triplets is useful for analyzing trends and patterns in data.

Solution

Here is sample code to check for increasing triplets:

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
boolean hasIncreasingTriplet(int[] arr) {
  
  for(int i=0; i<arr.length-2; i++) {
    if(arr[i] < arr[i+1] && arr[i+1] < arr[i+2]) {
      return true;
    }
  }
  
  return false;
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
bool hasIncreasingTriplet(vector<int> arr) {

  for(int i=0; i<arr.size()-2; i++) {
    if(arr[i] < arr[i+1] && arr[i+1] < arr[i+2]) {
      return true;
    }
  }

  return false;
}

Python

1
2
3
4
5
6
7
def has_increasing_triplet(arr):
  
  for i in range(len(arr)-2):  
    if arr[i] < arr[i+1] and arr[i+1] < arr[i+2]:
      return True

  return False

This checks each triplet of adjacent elements in order and returns true if an increasing subsequence of length 3 is found.

We can modify to return the triplets or count them by tracking indices. This pattern helps find trends.

Description

The concept of an “increasing triplet subsequence” refers to finding three numbers a[i], a[j], and a[k] in a given array such that i < j < k and a[i] < a[j] < a[k]. The challenge is often to do this in linear time, i.e., O(N), where N is the size of the array.

Solution

To find such a subsequence efficiently, we maintain two variables: first_min and second_min, initialized with the maximum value for the data type. We traverse the array once, updating these variables and checking for a valid third element that forms the triplet.

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
public class IncreasingTriplet {
    public static boolean increasingTriplet(int[] nums) {
        int first_min = Integer.MAX_VALUE, second_min = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num <= first_min) {
                first_min = num;
            } else if (num <= second_min) {
                second_min = num;
            } else {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        System.out.println(increasingTriplet(arr));  // Output: true
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <limits>
#include <vector>
using namespace std;

bool increasingTriplet(vector<int>& nums) {
    int first_min = INT_MAX, second_min = INT_MAX;
    for (int num : nums) {
        if (num <= first_min) {
            first_min = num;
        } else if (num <= second_min) {
            second_min = num;
        } else {
            return true;
        }
    }
    return false;
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    cout << (increasingTriplet(arr) ? "true" : "false") << endl;  // Output: true
    return 0;
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def increasingTriplet(nums):
    first_min, second_min = float('inf'), float('inf')
    for num in nums:
        if num <= first_min:
            first_min = num
        elif num <= second_min:
            second_min = num
        else:
            return True
    return False

if __name__ == "__main__":
    arr = [1, 2, 3, 4, 5]
    print(increasingTriplet(arr))  # Output: True

Key Takeaways

The problem asks for a linear-time solution, and the approach described achieves that by iterating through the array only once.
Two variables, first_min and second_min, hold the smallest and second smallest elements found so far, respectively.
If you find an element greater than second_min, then you’ve found the triplet.
The code remains consistent in its logic across Java, C++, and Python, with only language-specific syntax varying.