Maximum Increasing Triplet Value - Practice Coding Problems

Maximum Increasing Triplet Value - Problem

Given an integer array nums, return the maximum value of a triplet (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k].

The value of a triplet (i, j, k) is defined as nums[i] - nums[j] + nums[k].

If no such triplet exists, return 0.

Input & Output

Example 1 — Basic Increasing Triplet

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

› Output: 5

💡 Note: The optimal triplet is at indices (1,2,3) with values (1,3,4). Since 1 < 3 < 4, the triplet value is 1 - 3 + 4 = 2. However, we can also use (0,1,3) giving 2 - 1 + 4 = 5, which is maximum.

Example 2 — Multiple Valid Triplets

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

› Output: 4

💡 Note: Multiple triplets exist. The best is (0,1,4) with values (1,2,5), giving 1 - 2 + 5 = 4. Any triplet (i,j,k) with i < j < k works since array is strictly increasing.

Example 3 — No Valid Triplet

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

› Output: 0

💡 Note: Array is decreasing, so no triplet (i,j,k) exists where nums[i] < nums[j] < nums[k]. Return 0.

Constraints

3 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array [2,1,3,4] with indices 0,1,2,3

Find Valid Triplets

Check all i<j<k where nums[i]<nums[j]<nums[k]

Calculate Values

Compute nums[i]-nums[j]+nums[k] for each valid triplet

Key Takeaway

🎯 Key Insight: Maximize the first and last elements while minimizing the middle element in the triplet formula

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is to maximize nums[i] + nums[k] while minimizing nums[j] in the triplet formula. The optimal approach uses a single pass to track running minimums and maximum triplet values. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass Optimization	O(n)	O(1)	Track running minimums and maximums while scanning array once
Two Pass Optimization	O(n)	O(n)	Pre-compute maximum left and right values for each position
Brute Force - Three Nested Loops	O(n³)	O(1)	Check all possible triplets (i, j, k) and find maximum value

Single Pass Optimization — Algorithm Steps

Initialize minLeft as infinity and maxValue as 0
For each element, update the maximum triplet value if it can be the last element
Update minLeft to track minimum seen so far
Continue until end of array

Visualization

Tap to expand

Step-by-Step Walkthrough

Track Minimum

Keep track of minimum element seen so far

Track Max Difference

Maintain best (minLeft - middle) value

Update Result

For each element as rightmost, update maximum triplet value

Code -

solution.c — C

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

int solution(int* nums, int n) {
    if (n < 3) return 0;
    
    int maxValue = 0;
    int minLeft = INT_MAX;
    int maxLeftMinusMid = INT_MIN;
    
    for (int i = 0; i < n; i++) {
        if (maxLeftMinusMid != INT_MIN) {
            int candidate = maxLeftMinusMid + nums[i];
            if (candidate > maxValue) {
                maxValue = candidate;
            }
        }
        
        if (minLeft != INT_MAX) {
            int candidate = minLeft - nums[i];
            if (candidate > maxLeftMinusMid) {
                maxLeftMinusMid = candidate;
            }
        }
        
        if (nums[i] < minLeft) {
            minLeft = nums[i];
        }
    }
    
    return maxValue;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the array

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

847 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

Single Pass Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler