Increasing Triplet Subsequence
Problem Description
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:
Explanation: Any triplet where i < j < k is valid.
Example 2:
Explanation: No triplet exists.
Example 3:
Explanation: One of the valid triplet is index (3, 4, 5), because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.
Constraints:
- 1 <= nums.length <= 5 * 105
- -231 <= nums[i] <= 231 - 1
Follow up: Could you implement a solution that runs in O(n) time complexity and O(1) space complexity?
Solve it on LeetCode
Approaches
1. Brute Force Approach
Intuition:
The simplest approach to find an increasing triplet subsequence is to use three nested loops to check all possible triplets in the array.
This is a naive solution but helps to understand the underlying concept.
Code:
- Time Complexity: O(n^3), due to the three nested loops over the array.
- Space Complexity: O(1), since we are not using any additional data structures.
2. Linear Scan using Two Variables
Intuition:
The goal is to find three increasing numbers a, b, c such that a < b < c. We can achieve this in linear time with two variables:
- first: This will keep track of the smallest number found so far.
- second: This will keep track of a number larger than first.
As we scan through the array, the goal is to gradually refine these candidates. If at any point we encounter a number greater than both first and second, it becomes our third, and the triplet exists.
Why This Works
The key idea is that we’re not trying to find the actual triplet, we’re trying to prove that one exists.
The algorithm maintains the strongest possible candidates for forming an increasing triplet:
- first: We always keep
firstas small as possible. A smallerfirstincreases our chances of finding a validsecondandthird. - second: Once we have a good
first, we look for the smallest number greater thanfirst. This ensures the widest possible margin for finding a futurethird. - Encountering third: If we ever see a number greater than both
firstandsecond, we are guaranteed to have: first < second < num (this num is our c).
The moment this happens, we can immediately return true.
Code:
- Time Complexity: O(n), where n is the number of elements in the array. We only require one pass through the array.
- Space Complexity: O(1), since we are using only a constant amount of additional space.