LeetCode 334. Increasing Triplet Subsequence

Intuition

I had an intuition to use two pointer but it was too slow the answer was to use greedy approach to find i and j

1. Loop over nums
2. if we find the n that is less than or equal to i, i is now n
3. if we find n that is less than or equal to j and greater than i, j is now n
4. if we find that n greater than j and i, condition is satisfied and return True
5. if we didn't catch the condition return False

Optimal Solution

class Solution:
	def increasingTriplet(self, nums: List[int]) -> bool:
		first = float('inf')
		second = float('inf')

		for n in nums:
			if n <= first:
				first = n
			elif n <= second:
				second = n
			elif first < second < n:
				return True
		return False

Time Complexity

Time Complexity O(N)

Space Complexity O(1)