Please see github.com/anusha-murali for all of my repositories.
This is a nice problem from LeetCode (Problem #334)
Problem: 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
.
Solution
def increasingTriplet(nums):
first = second = float("inf")
for val in nums:
if val <= first:
first = val
elif val <= second:
second = val
else:
return True
return False
Proof: It’s clear that if we reach the else
part of the if
statement, the val
currently under consideration completes an increasing triplet.
It’s now sufficient to proof that when we reach the else
part, both first
and second
are already filled in and there were indeed two integers nums[i]
and nums[j]
with i < j
.
Since first
and second
were initialized to $\infty$, nums[0]
will be first assigned to first
. There are two cases to consider. Any subsequent value nums[j]
could be <= first
or > first
. If a subsequent value nums[j] > first
, then it will be assigned to second
. In this case, first == nums[i] < second == nums[j]
and i < j
and the proof is complete. In the second case, nums[j] < first
, which means nums[j] < second
. Hence we are free to update first
with nums[j]
, knowing that we have already found two numbers earlier such that first < second
, where the index of first
is smaller than the index of second
. This completes the proof.
It is important to note that even though the above code correctly identifies the presence of an increasing triplet, the triplet generated by the above code may not necessarily be a correct one. This is OK as the problem is not asking us to return the triplet.
Runtime: $O(n)$ as we iterate through nums
only once.
Back to String and Array Problems