Teaching Kids Programming: Videos on Data Structures and Algorithms
Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.
Example 1:
Input: nums = [1,2,3,4,5]
Output: true
Explanation: Any triplet where i < j < k is valid.Example 2:
Input: nums = [5,4,3,2,1]
Output: false
Explanation: No triplet exists.Example 3:
Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.Follow up: Could you implement a solution that runs in O(n) time complexity and O(1) space complexity?
Increasing Triplet Subsequence Bruteforce Algorithm
We can bruteforce every triplets in O(N^3).
1 2 3 4 5 6 7 8 9 | class Solution: def increasingTriplet(self, nums: List[int]) -> bool: n = len(nums) for i in range(n): for j in range(i + 1, n): for k in range(j + 1, n): if nums[i] < nums[j] < nums[k]: return True return False |
class Solution: def increasingTriplet(self, nums: List[int]) -> bool: n = len(nums) for i in range(n): for j in range(i + 1, n): for k in range(j + 1, n): if nums[i] < nums[j] < nums[k]: return True return False
Increasing Triplet Subsequence Algorithm (Linear)
We can save the first two numbers and if we find a number that is bigger than first two, we can return True. There is only one pass and thus O(N) time.
1 2 3 4 5 6 7 8 9 10 11 | class Solution: def increasingTriplet(self, nums: List[int]) -> bool: a = b = math.inf for i in nums: if i <= a: a = i elif i <= b: b = i else: return True return False |
class Solution: def increasingTriplet(self, nums: List[int]) -> bool: a = b = math.inf for i in nums: if i <= a: a = i elif i <= b: b = i else: return True return False
See the implementation of Increasing Subsequence Triplet in C++: The O(N) Increasing Triplet Subsequence Algorithm
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Longest Path in Binary Tree via Diameter Algorithm (DFS + BFS)
Next Post: Teaching Kids Programming - Two Pointer Algorithm to Capitalize the Title String