algoadvance

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 exist, return false.

Clarifying Questions

1. What is the range of elements in nums?
   • Typically, nums would range from -10^9 to 10^9, unless mentioned otherwise.
2. What is the range of the length of nums?
   • nums can be empty or have up to 10^5 elements.
3. Should the solution handle duplicate values in nums?
   • Yes, the solution should handle duplicate values properly.
4. Is there any specific time complexity requirement?
   • Ideally, we aim for a solution that is better than O(N^2). An optimal solution would be O(N) time complexity with O(1) space complexity.

Strategy

To solve this problem efficiently, we can maintain two variables:

• first: This keeps track of the smallest value encountered so far.
• second: This keeps track of the smallest value encountered after first.

The idea is to:

1. Traverse through the list.
2. Update first when a smaller value is found.
3. Update second if it is greater than first but less than the current value. When second is updated, it implies we have found the second number in the triplet.
4. If we encounter a value greater than both first and second, it means we have found our triplet.

Code

Here’s the Python function to implement the above logic:

def increasingTriplet(nums):
    first = second = float('inf')
    
    for n in nums:
        if n <= first:
            first = n  # smallest value
        elif n <= second:
            second = n  # second smallest value
        else:
            return True  # found a value bigger than both 'first' and 'second'
    
    return False

# Example Test Cases
print(increasingTriplet([1, 2, 3, 4, 5]))  # Expected output: True
print(increasingTriplet([5, 4, 3, 2, 1]))  # Expected output: False
print(increasingTriplet([2, 1, 5, 0, 4, 6]))  # Expected output: True

Time Complexity

• Time Complexity: O(N), where N is the length of the array nums. This is because we are doing a single pass over the array.
• Space Complexity: O(1), as we are using only a fixed amount of extra space.

This efficient solution meets the requirements and constraints of the problem statement.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?