Increasing Triplet Sequence

This is a nice problem from LeetCode (Problem #334)

Problem: 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 exists, return false.

Example 1:

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

Explanation: Any triplet where $i < j < k$ is valid.

Example 2:

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

Explanation: No triplet exists.

Example 3:

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

Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

Solution

    def increasingTriplet(nums):
        first = second = float("inf")
        for val in nums:
            if val <= first:
                first = val
            elif val <= second:
                second = val
            else:
                return True
        return False

Proof: It’s clear that if we reach the else part of the if statement, the val currently under consideration completes an increasing triplet.

It’s now sufficient to proof that when we reach the else part, both first and second are already filled in and there were indeed two integers nums[i] and nums[j] with i < j.

Since first and second were initialized to $\infty$, nums[0] will be first assigned to first. There are two cases to consider. Any subsequent value nums[j] could be <= first or > first. If a subsequent value nums[j] > first, then it will be assigned to second. In this case, first == nums[i] < second == nums[j] and i < j and the proof is complete. In the second case, nums[j] < first, which means nums[j] < second. Hence we are free to update first with nums[j], knowing that we have already found two numbers earlier such that first < second, where the index of first is smaller than the index of second. This completes the proof.

It is important to note that even though the above code correctly identifies the presence of an increasing triplet, the triplet generated by the above code may not necessarily be a correct one. This is OK as the problem is not asking us to return the triplet.

Runtime: $O(n)$ as we iterate through nums only once.

Back to String and Array Problems

---

anusha-murali.github.io