Teaching Kids Programming – Increasing Triplet Subsequence Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Follow up: Could you implement a solution that runs in O(n) time complexity and O(1) space complexity?

Increasing Triplet Subsequence Bruteforce Algorithm

We can bruteforce every triplets in O(N^3).

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if nums[i] < nums[j] < nums[k]:
                        return True
        return False

Increasing Triplet Subsequence Algorithm (Linear)

We can save the first two numbers and if we find a number that is bigger than first two, we can return True. There is only one pass and thus O(N) time.

 class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        a = b = math.inf
        for i in nums:
            if i <= a:
                a = i
            elif i <= b:
                b = i
            else:
                return True
        return False

See the implementation of Increasing Subsequence Triplet in C++: The O(N) Increasing Triplet Subsequence Algorithm

–EOF (The Ultimate Computing & Technology Blog) —