Tried this but not a right solution
/**
* @param {number[]} nums
* @return {boolean}
*/
var increasingTriplet = function(nums) {
for(let i = 0 ; i<nums.length-2;i++){
let a = i;
let b = i+1;
let c = i+2
if(nums[i]<nums[i+1] && nums[i+1]<nums[i+2]){
return true
}
}
return false
};
Some cases will fail with the above solution because we should not be finding consecutive triplets
Brute Force Approach
It's easy to use Brute Force way to solve this problem, but the time complexity is O(n3), it will TLE, so we need to find a better way.
public static boolean increasingTriplet(int[] nums) {
if (nums == null || nums.length < 3) {
return false;
}
int len = nums.length;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
for (int k = j + 1; k < len; k++) {
if (nums[i] < nums[j] && nums[j] < nums[k]) {
return true;
}
}
}
}
return false;
}
Two Pointer Approach
When traversing the array nums[j], 0<j<n−1, if there is an element on the left of nums[i]<nums[j], 0≤i<j, and an element on the right of nums[k], j<k<len.
Therefore, we can maintain the minimum value on the left and the maximum value on the right of each element in the array.
/**
* @param {number[]} nums
* @return {boolean}
*/
var increasingTriplet = function(nums) {
let l = nums.length;
let leftMin = new Array(l).fill(Infinity)
let rightMax = new Array(l).fill(-Infinity)
leftMin[0] = nums[0];
rightMax[l-1] = nums[l-1];
for(let i=1;i<l;i++){
leftMin[i] = Math.min(leftMin[i-1],nums[i])
}
for(let j=l-2;j>0;j--){
rightMax[j] = Math.max(rightMax[j+1],nums[j])
}
for(let k =0 ;k<l;k++){
if(nums[k]> leftMin[k] && nums[k]<rightMax[k]){
return true;
}
}
return false
};
Greedy Approach
A greedy algorithm builds up a solution piece by piece, always choosing the next piece that offers the most immediate benefit. It doesn't look ahead to see if future steps could be improved by a different choice; instead, it makes a choice that looks best at the moment.
Basically as we are iterating we should be needing 2 more numbers lesser than it ie firstNumber, secondNumber . like firstNumber < secondNumber < CurrentNumber.
/**
* @param {number[]} nums
* @return {boolean}
*/
var increasingTriplet = function(nums) {
let firstNumber = Infinity
let secondNumber = Infinity
for(currentNumber of nums){
if(currentNumber > firstNumber && currentNumber > secondNumber ){
return true
}
if ( currentNumber > firstNumber ){
secondNumber = currentNumber
}else {
firstNumber = currentNumber
}
}
return false
};
This can be reconfigured as arri > arrj > arrk. Since we are already tracking currentNumber on each iteration, we only need to track two other numbers to get our (potential) triplet:
var increasingTriplet = function(nums) {
let firstNumber = Infinity;
let secondNumber = Infinity;
for (let currentNumber of nums) {
We can start at Infinity for the two minimum numbers, since we'll want to grab the first two number we come across.
Success Condition
We should be able to reach a state where currentNumber (set as arr[i] in our algorithm) is greater than the first and second-most minimum numbers.
if (currentNumber > secondNumber && currentNumber > firstNumber) {
return true;
}
That is, if at any point in the loop, we find a number that is greater than our two stored numbers, then we automatically have a valid triplet. Thus, we can return true.
Tracking Minimum Numbers
We need to track two other numbers to make a subsequence with currentNumber.
if (currentNumber > firstNumber) {
secondNumber = currentNumber;
} else {
firstNumber = currentNumber;
}
Basically, this conditional ensures that we always have the lowest number in the array stored as firstNumber. Then, each time we encounter a number that's larger than firstNumber, we store that number and continue.
The reason this works is that if we ever find another number that's larger than secondNumber, then we have our triplet and our first conditional triggers and returns true for us.
By the end of all this, if we never find that third (or second!) increasing number, then it doesn't exist in our list and we return false.
Why It’s Greedy:
Local Optimal Choice: At each step, the algorithm makes a local optimal choice by updating firstNumber and secondNumber with the smallest values that can still potentially form an increasing triplet. This choice is made without considering future elements beyond the current step.
Immediate Feedback: The algorithm immediately checks if the current number can complete an increasing triplet by comparing it with firstNumber and secondNumber. If it finds such a number, it returns true immediately.
Learnings in JS Syntax
we could use Infinity to represent large number
we could use of property for for loops
Credits to : https://leetcode.com/u/garrowat/
Top comments (1)
please follow for more content , also do comment the complexities for two pointer approach