Leetcode - 334. Increasing Triplet Subsequence

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/