Problem
Given an integer array nums, returntrue if there exist three indices i < j < k such that nums[i] < nums[j] < nums[k]. Otherwise, return false.
The solution should run in
O(n) time and use O(1) extra space.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [1,2,3,4,5]Output
trueSolution
This solution uses two variables to track the smallest and second smallest values seen so far.As we traverse the array, if the current number is greater than
secondSmallest, we have found three values in increasing order.
If the current number is greater than
smallest, it becomes the new second smallest.
Otherwise, it becomes the new smallest. This allows us to find the increasing triplet in a single pass without storing additional elements.
class Solution {
public boolean increasingTriplet(int[] nums) {
if (nums.length < 3)
return false;
int smallest = Integer.MAX_VALUE;
int secondSmallest = Integer.MAX_VALUE;
for (int num : nums) {
// Found three increasing values
if (num > secondSmallest)
return true;
else if (num > smallest)
secondSmallest = num;
else
smallest = num;
}
return false;
}
}
Complexity
The array is traversed only once, so the overall time complexity isO(n). Only two variables are used to track the smallest values, so the space complexity is O(1).