Problem Description

You are given an integer array nums. Your task is to determine if there exists an increasing triplet subsequence in the array.

An increasing triplet subsequence means finding three indices i, j, and k such that:

• The indices are in strictly increasing order: i < j < k
• The values at these indices are also in strictly increasing order: nums[i] < nums[j] < nums[k]

If such a triplet exists anywhere in the array, return true. Otherwise, return false.

The key insight of the solution is to maintain two variables while scanning through the array:

• mi: tracks the smallest value seen so far
• mid: tracks the smallest value that is greater than mi

As we iterate through each number:

• If we find a number greater than mid, we've found our increasing triplet (since we already have mi < mid < current number)
• If the number is less than or equal to mi, we update mi to this smaller value
• Otherwise, the number must be between mi and mid, so we update mid

This greedy approach works because we're always maintaining the smallest possible values for the first two elements of a potential triplet, maximizing our chances of finding a valid third element.

Intuition

The naive approach would be to check every possible triplet using three nested loops, which would take O(n³) time. We need something more efficient.

Let's think about what we're really looking for: three numbers in increasing order where their positions also increase. As we scan through the array, at any point, we want to know: "Can I form an increasing triplet ending at the current position?"

To form such a triplet, we need two smaller numbers before the current position. But here's the key insight: we don't need to track all possible pairs of smaller numbers. We only need to track the best possible pair - the one most likely to help us find a valid triplet.

What makes a pair "best"? If we have the smallest possible first element and the smallest possible second element (that's still greater than the first), we maximize our chances of finding a third element that's greater than both.

Think of it like building stairs:

• We want the first step (mi) to be as low as possible
• We want the second step (mid) to be as low as possible while still being higher than the first
• Then any number higher than the second step completes our staircase

This leads us to the greedy strategy: maintain two variables representing the smallest and second-smallest values we've seen so far in a way that preserves the increasing relationship. When we encounter a number:

• If it's bigger than our second-smallest (mid), we've found our triplet!
• If it's the smallest we've seen, update our first step
• If it's between our first and second steps, update our second step to make it lower (better for future comparisons)

This way, we only need one pass through the array with O(1) space, achieving O(n) time complexity.

Solution Approach

We implement the greedy strategy using two variables to track the smallest possible values for a potential increasing triplet:

1. Initialize two trackers:

   • mi = inf: Represents the smallest value seen so far (potential first element of triplet)
   • mid = inf: Represents the smallest value greater than mi (potential second element of triplet)

2. Iterate through each number in the array:

   for num in nums:

3. Check three conditions for each number:

   Condition 1: Found the third element

   if num > mid:
       return True

   If the current number is greater than mid, we've found our increasing triplet. Why? Because:

   • We already have mi < mid (by construction)
   • Now we have num > mid
   • Therefore: mi < mid < num forms a valid triplet

   Condition 2: Update the smallest value

   if num <= mi:
       mi = num

   If the current number is less than or equal to mi, update mi. This keeps our first potential element as small as possible, maximizing chances for finding valid second and third elements later.

   Condition 3: Update the middle value

   else:
       mid = num

   If the number is between mi and mid (greater than mi but not greater than mid), update mid. This maintains the relationship mi < mid while keeping mid as small as possible.

4. Return false if no triplet found:

   return False

   If we complete the iteration without finding a valid triplet, return False.

The algorithm maintains the invariant that mi and mid always represent the best possible pair of values for forming an increasing triplet, where "best" means having the smallest possible values while maintaining mi < mid.

Example Walkthrough

Let's trace through the algorithm with the array nums = [2, 1, 5, 0, 4, 6].

Initial state:

• mi = inf
• mid = inf

Step 1: Process num = 2

• Is 2 > mid (inf)? No
• Is 2 <= mi (inf)? Yes → Update mi = 2
• State: mi = 2, mid = inf

Step 2: Process num = 1

• Is 1 > mid (inf)? No
• Is 1 <= mi (2)? Yes → Update mi = 1
• State: mi = 1, mid = inf

Step 3: Process num = 5

• Is 5 > mid (inf)? No
• Is 5 <= mi (1)? No
• Since 5 > mi (1) and 5 <= mid (inf) → Update mid = 5
• State: mi = 1, mid = 5
• We now have a potential pair: 1 < 5

Step 4: Process num = 0

• Is 0 > mid (5)? No
• Is 0 <= mi (1)? Yes → Update mi = 0
• State: mi = 0, mid = 5
• Note: We still keep mid = 5 even though mi changed. This is crucial - mid was set when mi was 1, and the relationship 1 < 5 still exists in the array.

Step 5: Process num = 4

• Is 4 > mid (5)? No
• Is 4 <= mi (0)? No
• Since 4 > mi (0) and 4 <= mid (5) → Update mid = 4
• State: mi = 0, mid = 4
• We improved our middle value to a smaller one while maintaining the increasing property.

Step 6: Process num = 6

• Is 6 > mid (4)? Yes! → Return True
• We found our triplet! While our current mi = 0 and mid = 4, the actual triplet in the array is formed by the indices where:
  • First element: 1 (at index 1)
  • Second element: 5 or 4 (at index 2 or 4)
  • Third element: 6 (at index 5)

The beauty of this algorithm is that we don't need to track the actual indices. We just need to know that at some point we had values satisfying first < second, and now we found a third > second, guaranteeing an increasing triplet exists.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input array nums. The algorithm makes a single pass through the array, performing constant-time operations (comparisons and assignments) for each element.

Space Complexity: O(1) - The algorithm uses only two extra variables (mi and mid) to track the smallest and middle values of a potential increasing triplet, regardless of the input size. No additional data structures that scale with input size are used.

Common Pitfalls

Pitfall 1: Misunderstanding the Variable Updates

The Problem: A common misconception is thinking that when we update mi to a new smaller value, we lose track of the previous valid pair (mi, mid). Students often worry: "If I update mi after finding a valid mid, won't I break the existing relationship?"

Example of the Confusion: Consider the array [5, 1, 6, 2, 7]:

• Initially: mi = 5, mid = inf
• After 1: mi = 1 (updated from 5)
• After 6: mid = 6 (now mi = 1, mid = 6)
• After 2: mi = 1, mid = 2 (updated mid)
• After 7: Found triplet! (1 < 2 < 7)

Some might incorrectly think: "Wait, but the actual triplet in order is 5 < 6 < 7, not 1 < 2 < 7. Is this valid?"

The Solution: The algorithm doesn't track the actual indices or preserve the exact triplet elements. Instead, it maintains that:

• There exists some value before the current position that could be the first element
• There exists another value after that first one that could be the second element
• We're looking for a third element greater than both

The key insight: Once we establish that a valid (mi, mid) pair exists somewhere in the array, updating mi to a smaller value doesn't invalidate that a pair existed - it just gives us a better chance of finding a third element.

Pitfall 2: Incorrect Condition Order

The Problem: Changing the order of the if-conditions can break the algorithm. For instance:

# WRONG ORDER
for num in nums:
    if num <= mi:
        mi = num
    elif num <= mid:
        mid = num
    elif num > mid:
        return True

Why This Fails: The condition num > mid should be checked first. If we update mi or mid before checking if num could be our third element, we might miss valid triplets.

The Solution: Always check conditions in this specific order:

1. First check if num > mid (found triplet)
2. Then check if num <= mi (update smallest)
3. Finally, handle the middle case (update mid)

Pitfall 3: Using Strict Inequality for the First Update

The Problem: Using num < mi instead of num <= mi:

# INCORRECT
if num < mi:  # Should be num <= mi
    mi = num

Why This Matters: Consider [1, 1, 1, 1, 2, 3]. If we use strict inequality:

• After first 1: mi = 1
• After second 1: We don't update mi, so we set mid = 1
• This incorrectly establishes mi = 1, mid = 1 when we need mi < mid

The Solution: Use num <= mi to ensure duplicate values don't create false pairs. When we see a value equal to mi, we should update mi rather than mid to maintain the strict inequality requirement between elements of the triplet.