Sponsored
Sponsored
This approach leverages two variables to track the smallest and the second smallest elements found so far in the array. As you traverse through the array, you update these two variables. If you find an element greater than the second smallest, then a triplet exists, and you return true.
Time Complexity: O(n), where n is the length of the input list, as we only traverse the list once.
Space Complexity: O(1), since we are using only a constant amount of extra space.
1#include <stdbool.h>
2#include <limits.h>
3
4bool increasingTriplet(int* nums, int numsSize) {
5 int first = INT_MAX, second = INT_MAX;
6 for (int i = 0; i < numsSize; i++) {
7 if (nums[i] <= first) {
8 first = nums[i];
9 } else if (nums[i] <= second) {
10 second = nums[i];
11 } else {
12 return true;
13 }
14 }
15 return false;
16}This C solution iterates over the array, updating two variables, first and second, that keep track of the smallest and second smallest values. If a current element is greater than second, it confirms the existence of an increasing triplet.
This approach uses an auxiliary array to keep track of the minimum elements on the left and the maximum elements on the right for each position in the array. The main idea is to check if there's any element that can serve as the middle element between some smaller and a larger element.
Time Complexity: O(n), due to traversals of size n.
Space Complexity: O(n), since it uses extra space for two arrays.
1class Solution {
2 public
This Java solution calculates leftMin and rightMax to determine if an element in the middle can form an increasing triplet.