Increasing Triplet Subsequence - Practice Coding Problems

Increasing Triplet Subsequence - Problem

Array Greedy Medium

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

If no such indices exist, return false.

Follow up: Can you implement a solution that runs in O(n) time complexity and O(1) space complexity?

Input & Output

Example 1 — Increasing Sequence

$ Input: nums = [1,2,3,4,5]

› Output: true

💡 Note: Any triplet (i,j,k) with i < j < k satisfies the condition. For instance, (0,1,2) gives us 1 < 2 < 3.

Example 2 — No Valid Triplet

$ Input: nums = [5,4,3,2,1]

› Output: false

💡 Note: No triplet satisfies the condition since the array is decreasing.

Example 3 — Mixed Values

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

› Output: true

💡 Note: The triplet (1,4,5) gives indices with values 1 < 4 < 6.

Constraints

1 ≤ nums.length ≤ 5 × 10⁵
-2³¹ ≤ nums[i] ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given integer array with various values

Find Pattern

Look for i < j < k where nums[i] < nums[j] < nums[k]

Output

Return true if such triplet exists, false otherwise

Key Takeaway

🎯 Key Insight: Use greedy approach to track only the two smallest values seen so far

Asked in

f Facebook 42 G Google 38 a Amazon 31 M Microsoft 25

The key insight is to use a greedy approach tracking only two variables: the smallest value seen so far and the second smallest. When we find any value larger than both, we immediately know an increasing triplet exists. Best approach is the greedy two-variable method with Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Two Variables	O(n)	O(1)	Track the smallest and second smallest values in one pass
Brute Force	O(n³)	O(1)	Check all possible triplets with three nested loops

Greedy Two Variables — Algorithm Steps

Initialize first and second to infinity
For each number, update first if it's smaller than first
Else if number is smaller than second, update second
Else if number is larger than second, we found a triplet

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set first = ∞, second = ∞

Update Variables

Update first and second as we scan

Found Triplet

When we find num > second, return true

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <limits.h>

bool solution(int* nums, int numsSize) {
    int first = INT_MAX;
    int second = INT_MAX;
    
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] <= first) {
            first = nums[i];
        } else if (nums[i] <= second) {
            second = nums[i];
        } else {
            return true;
        }
    }
    
    return false;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    bool result = solution(nums, numsSize);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the array with constant work per element

✓ Linear Growth

Space Complexity

O(1)

Only using two variables to track smallest and second smallest values

✓ Linear Space

205.4K Views

High Frequency

~15 min Avg. Time

6.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Two Variables — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler