Introduction

The problem is to find indices i, j, and k such that i < j < k and arr[i] < arr[j] < arr[k], while still running in linear time. The usual trick is to precompute whether each position has a smaller value on its left and a larger value on its right, then scan once for a valid middle element.

Why A Naive Solution Is Too Slow

The brute-force approach checks every triple of indices, which costs O(n^3). Even a partially improved approach that fixes the middle element and searches left and right repeatedly can still degrade badly.

To stay in O(n), we need to preserve enough information from earlier and later positions so each index can be tested in constant time.

Build Left-Smaller And Right-Greater Arrays

The standard linear-time approach uses two helper arrays:

• 'left_smaller[j] stores the index of a smaller value that appears before j, or -1 if none exists'
• 'right_greater[j] stores the index of a larger value that appears after j, or -1 if none exists'

Once those arrays are built, any position j with both values present is the middle of a valid increasing triplet.

1def find_increasing_triplet(arr):
2    n = len(arr)
3    if n < 3:
4        return None
5
6    left_smaller = [-1] * n
7    right_greater = [-1] * n
8
9    min_index = 0
10    for i in range(1, n):
11        if arr[i] <= arr[min_index]:
12            min_index = i
13        else:
14            left_smaller[i] = min_index
15
16    max_index = n - 1
17    for i in range(n - 2, -1, -1):
18        if arr[i] >= arr[max_index]:
19            max_index = i
20        else:
21            right_greater[i] = max_index
22
23    for j in range(n):
24        if left_smaller[j] != -1 and right_greater[j] != -1:
25            i = left_smaller[j]
26            k = right_greater[j]
27            return (arr[i], arr[j], arr[k]), (i, j, k)
28
29    return None
30
31
32print(find_increasing_triplet([12, 11, 10, 5, 6, 2, 30]))
33print(find_increasing_triplet([5, 4, 3, 2, 1]))

This runs in O(n) time and uses O(n) extra space.

How The Helper Arrays Work

The left-to-right pass keeps track of the index of the smallest value seen so far. If the current element is greater than that minimum, then the minimum index becomes a valid left partner for the current position.

The right-to-left pass mirrors the idea. It keeps the index of the largest value seen to the right. If the current value is smaller than that maximum, then the maximum index becomes a valid right partner.

The final scan simply asks: "Is there a valid smaller value before this position and a valid larger value after it?" If yes, the triplet exists and the current element is the middle value.

Example Walkthrough

Take this array:

arr = [12, 11, 10, 5, 6, 2, 30]

At index 4, the value is 6. The left-to-right pass has already recorded that 5 at index 3 is a smaller earlier value. The right-to-left pass has recorded that 30 at index 6 is a larger later value.

So index 4 is a valid middle position, and the algorithm can return the triplet (5, 6, 30) with indices (3, 4, 6).

This is the key insight: you do not need to enumerate every candidate triplet. You only need to know whether each position can serve as the middle.

Existence Versus Reconstruction

If the problem only asks whether such a triplet exists, you can sometimes use even less information. But if you want to return the actual numbers or indices, storing left and right helper arrays makes reconstruction straightforward.

That is why this O(n) plus O(n) approach remains a popular interview and implementation answer: it is efficient and it returns a concrete triplet without extra searching.

Common Pitfalls

• Checking only values and forgetting that the indices must also be in increasing order.
• Using strictly less-than conditions inconsistently when duplicates are present.
• Recomputing smaller-left or larger-right information inside the final scan and losing the linear-time guarantee.
• Returning the first three increasing values you see without verifying their index ordering.
• Confusing an existence-only optimization with an algorithm that must return the actual triplet.

Summary

• A valid solution needs both increasing values and increasing indices.
• The linear-time approach precomputes whether each index has a smaller value on the left and a larger value on the right.
• Any index with both helpers present is a valid middle element of the triplet.
• This gives O(n) time and a direct way to reconstruct the actual answer.