# LeetCode 334: Increasing Triplet Subsequence

## Problem Restatement

We are given an integer array `nums`.

Return `true` if there exists an increasing subsequence of length `3`.

That means we need indices:

```text
i < j < k
```

such that:

```text
nums[i] < nums[j] < nums[k]
```

The elements do not need to be consecutive. They only need to appear in increasing index order.

The problem asks for:

| Requirement | Value |
|---|---|
| Time complexity | `O(n)` |
| Extra space | `O(1)` |

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | `true` if an increasing triplet exists |
| Required order | `i < j < k` |
| Required values | `nums[i] < nums[j] < nums[k]` |

Function shape:

```python
def increasingTriplet(nums: list[int]) -> bool:
    ...
```

## Examples

Example 1:

```text
Input: nums = [1,2,3,4,5]
Output: true
```

One valid triplet is:

```text
1 < 2 < 3
```

Example 2:

```text
Input: nums = [5,4,3,2,1]
Output: false
```

The sequence is strictly decreasing, so no increasing triplet exists.

Example 3:

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

One valid triplet is:

```text
0 < 4 < 6
```

## First Thought: Try All Triplets

A direct approach is:

1. Choose index `i`.
2. Choose index `j > i`.
3. Choose index `k > j`.
4. Check whether:

```text
nums[i] < nums[j] < nums[k]
```

This checks every possible triplet.

```text
O(n^3)
```

This is far too slow.

We need something linear.

## Key Insight

We do not need to remember all previous numbers.

We only need to track:

| Variable | Meaning |
|---|---|
| `first` | Smallest value seen so far |
| `second` | Smallest possible second value of an increasing pair |

The goal is to eventually find a number larger than `second`.

If we do, then we already have:

```text
first < second < current
```

which forms an increasing triplet.

The greedy idea is:

1. Keep `first` as small as possible.
2. Keep `second` as small as possible after `first`.

Smaller values make it easier to find a larger third value later.

## Algorithm

Initialize:

```python
first = infinity
second = infinity
```

Then scan the array from left to right.

For each number `x`:

1. If `x <= first`, update `first`.
2. Else if `x <= second`, update `second`.
3. Else:
   1. We found:

```text
first < second < x
```

   2. Return `True`.

If the loop ends without finding such a value, return `False`.

## Walkthrough

Use:

```text
nums = [2,1,5,0,4,6]
```

Start:

```text
first = inf
second = inf
```

Read `2`:

```text
first = 2
```

Read `1`:

```text
first = 1
```

Smaller first value is better.

Read `5`:

```text
second = 5
```

Now we have an increasing pair:

```text
1 < 5
```

Read `0`:

```text
first = 0
```

This improves the smallest value.

Read `4`:

```text
second = 4
```

Now we have a better increasing pair:

```text
0 < 4
```

Read `6`.

Since:

```text
6 > second
```

we found:

```text
0 < 4 < 6
```

Return `True`.

## Why Updating `first` Does Not Break Things

A common confusion is:

```text
What if second was chosen before first changed?
```

Example:

```text
[2,1,5,0,4,6]
```

Initially:

```text
first = 1
second = 5
```

Later:

```text
first = 0
```

Now `second = 5` came before `0`.

Does that break the logic?

No.

Because later we update:

```text
second = 4
```

The algorithm always maintains the best possible increasing pair seen so far.

The pair represented by `(first, second)` always appears in valid order inside the scanned prefix.

## Correctness

The algorithm maintains these invariants while scanning the array:

| Invariant | Meaning |
|---|---|
| `first` | Smallest value seen so far |
| `second` | Smallest value greater than `first` seen so far |

When processing a value `x`:

If:

```text
x <= first
```

then replacing `first` with `x` is always safe, because a smaller first value makes future triplets easier to form.

If:

```text
first < x <= second
```

then replacing `second` with `x` is safe because we now have a smaller increasing pair:

```text
first < x
```

A smaller second value increases the chance of finding a future third value larger than it.

If:

```text
x > second
```

then we already have:

```text
first < second < x
```

with indices in increasing order because `first` and `second` were formed during earlier iterations.

Therefore, an increasing triplet subsequence exists.

If the algorithm finishes without reaching the third case, then no increasing triplet exists in the array.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | One scan through the array |
| Space | `O(1)` | Only two variables are stored |

## Implementation

```python
class Solution:
    def increasingTriplet(self, nums: list[int]) -> bool:
        first = float("inf")
        second = float("inf")

        for x in nums:
            if x <= first:
                first = x

            elif x <= second:
                second = x

            else:
                return True

        return False
```

## Code Explanation

Initialize the two tracking values:

```python
first = float("inf")
second = float("inf")
```

They represent the smallest values found so far.

For each number:

```python
for x in nums:
```

If `x` is smaller than or equal to `first`, update `first`:

```python
if x <= first:
    first = x
```

Otherwise, if `x` improves the second value:

```python
elif x <= second:
    second = x
```

Now we have a better increasing pair.

Otherwise:

```python
else:
    return True
```

This means:

```text
x > second > first
```

So an increasing triplet exists.

If the loop ends, no such triplet was found.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.increasingTriplet([1, 2, 3, 4, 5]) == True
    assert s.increasingTriplet([5, 4, 3, 2, 1]) == False
    assert s.increasingTriplet([2, 1, 5, 0, 4, 6]) == True

    assert s.increasingTriplet([1, 1, 1, 1]) == False
    assert s.increasingTriplet([1, 2]) == False
    assert s.increasingTriplet([1, 2, 2, 3]) == True
    assert s.increasingTriplet([20, 100, 10, 12, 5, 13]) == True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Increasing array | Simple valid triplet |
| Decreasing array | No valid triplet |
| Mixed values | Standard greedy example |
| Duplicate values | Strict inequality matters |
| Too short | Need at least three values |
| Repeated middle value | Handles duplicates correctly |
| Late triplet | Triplet appears after resets |