Jobs

Interviews

Discussions

Increasing Triplet Subsequence

Medium

Asked by:

More companies

25 views

Topics:

Arrays

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.

Constraints:

1 <= nums.length <= 5 * 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1

Follow up: Could you implement a solution that runs in O(n) time complexity and O(1) space complexity?

Try coding it in LeetCode

Increasing Triplet Subsequence

Medium

Asked by:

More companies

25 views

Topics:

Arrays

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.

Constraints:

1 <= nums.length <= 5 * 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1

Follow up: Could you implement a solution that runs in O(n) time complexity and O(1) space complexity?

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible size of the input array `nums`?
Can the input array `nums` contain negative integers, zero, or only positive integers?
Are duplicate numbers allowed in the input array `nums` and if so, how should they be handled?
If multiple increasing triplets exist, should I return `true` as soon as I find one?
Can I assume that the input array `nums` will never be null or empty?

Brute Force Solution

Approach

We're trying to find three numbers that get bigger in a sequence. The brute force method involves checking every possible combination of three numbers to see if they fit the rule.

Here's how the algorithm would work step-by-step:

Look at the first number in the list.
Then, for each number after the first, see if it's bigger than the first number.
If you find one that's bigger, look at all the numbers that come after that second number.
Check if any of those numbers are bigger than the second number.
If you find a third number that's bigger than the second, then you've found your increasing sequence of three numbers.
If you don't find such a sequence after checking all possibilities starting with the first number, repeat the whole process starting with the second number in the list, and so on.
Keep doing this until you either find a sequence or you've checked all possible starting points.

Code Implementation

def increasing_triplet_subsequence_brute_force(numbers):
    list_length = len(numbers)

    for first_index in range(list_length - 2):
        first_number = numbers[first_index]

        for second_index in range(first_index + 1, list_length - 1):
            second_number = numbers[second_index]

            # Ensure the second number is greater than the first
            if second_number > first_number:

                for third_index in range(second_index + 1, list_length):
                    third_number = numbers[third_index]

                    # Final check for triplet completion
                    if third_number > second_number:
                        return True

    # No increasing triplet found after all iterations
    return False

Big(O) Analysis

Time Complexity

O(n^3) – The described brute force approach iterates through all possible triplets in the array. The outer loop iterates up to n elements. The second loop iterates up to n elements for each element in the first loop, searching for a larger element. The inner loop then iterates up to n elements for each element in the second loop, searching for yet a larger element. Therefore the number of operations is proportional to n * n * n, which gives a time complexity of O(n^3).

Space Complexity

O(1) – The brute force approach described does not use any auxiliary data structures like arrays, hashmaps, or sets to store intermediate results. It only involves iterating through the input list and comparing elements directly. Therefore, the space used is constant and independent of the input size N. The only extra memory consumed consists of a few integer variables for indices, which is constant space.

Optimal Solution

Approach

The goal is to find if there are three numbers that appear in order, where each number is bigger than the one before it. Instead of checking all combinations, we keep track of the smallest two numbers we've seen so far and use those to quickly determine if we've found our increasing sequence.

Here's how the algorithm would work step-by-step:

Keep track of the smallest number you've seen up to this point.
Keep track of the second smallest number you've seen, making sure it's bigger than the smallest.
Go through the list of numbers one by one.
If you find a number smaller than the smallest number, update the smallest number.
If you find a number bigger than the smallest number, but smaller than the second smallest number, update the second smallest number.
If you find a number that's bigger than both the smallest and second smallest, you've found your increasing sequence, so you can stop and say it's true.
If you get to the end of the list without finding a third, bigger number, then you didn't find an increasing sequence, so it's false.

Code Implementation

def increasing_triplet_subsequence(numbers) -> bool:
    smallest_number_seen = float('inf')
    second_smallest_number_seen = float('inf')

    for number in numbers:
        if number <= smallest_number_seen:
            # Found a new smallest number
            smallest_number_seen = number

        elif number <= second_smallest_number_seen:
            # Found a new second smallest number
            second_smallest_number_seen = number

        else:
            # We found a number bigger than
            # both smallest and second smallest
            return True

    # If we didn't find a triplet
    return False

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array nums of size n exactly once. In each iteration, it performs a constant number of comparisons and assignments to track the smallest and second smallest numbers seen so far. Therefore, the time complexity is directly proportional to the size of the input array, resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The provided algorithm only uses a fixed number of variables to store the smallest and second smallest numbers encountered so far. The space required does not depend on the size of the input array (N). Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Empty or null input array	Return false immediately since a triplet cannot exist.
Array with fewer than 3 elements	Return false immediately since a triplet cannot exist.
Array with all identical values	The algorithm should correctly return false as no strictly increasing subsequence is possible.
Array sorted in descending order	The algorithm should correctly return false as no strictly increasing subsequence is possible.
Array with a long decreasing sequence followed by increasing elements	The algorithm should eventually find the increasing elements and return true if a triplet is formed.
Array contains very large or very small integers (potential for overflow in naive approaches)	The chosen algorithm should avoid arithmetic operations that could lead to overflow, preferring comparisons.
Array with duplicates interspersed amongst increasing values	The algorithm's logic should handle duplicates correctly, ensuring the subsequence is strictly increasing even with repeated values.
Large array size (scalability considerations)	The algorithm should have a time complexity of O(n) to handle large arrays efficiently; approaches with higher complexity will be less suitable.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible size of the input array `nums`?
Can the input array `nums` contain negative integers, zero, or only positive integers?
Are duplicate numbers allowed in the input array `nums` and if so, how should they be handled?
If multiple increasing triplets exist, should I return `true` as soon as I find one?
Can I assume that the input array `nums` will never be null or empty?

Brute Force Solution

Approach

We're trying to find three numbers that get bigger in a sequence. The brute force method involves checking every possible combination of three numbers to see if they fit the rule.

Here's how the algorithm would work step-by-step:

Look at the first number in the list.
Then, for each number after the first, see if it's bigger than the first number.
If you find one that's bigger, look at all the numbers that come after that second number.
Check if any of those numbers are bigger than the second number.
If you find a third number that's bigger than the second, then you've found your increasing sequence of three numbers.
If you don't find such a sequence after checking all possibilities starting with the first number, repeat the whole process starting with the second number in the list, and so on.
Keep doing this until you either find a sequence or you've checked all possible starting points.

Code Implementation

def increasing_triplet_subsequence_brute_force(numbers):
    list_length = len(numbers)

    for first_index in range(list_length - 2):
        first_number = numbers[first_index]

        for second_index in range(first_index + 1, list_length - 1):
            second_number = numbers[second_index]

            # Ensure the second number is greater than the first
            if second_number > first_number:

                for third_index in range(second_index + 1, list_length):
                    third_number = numbers[third_index]

                    # Final check for triplet completion
                    if third_number > second_number:
                        return True

    # No increasing triplet found after all iterations
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Keep track of the smallest number you've seen up to this point.
Keep track of the second smallest number you've seen, making sure it's bigger than the smallest.
Go through the list of numbers one by one.
If you find a number smaller than the smallest number, update the smallest number.
If you find a number bigger than the smallest number, but smaller than the second smallest number, update the second smallest number.
If you find a number that's bigger than both the smallest and second smallest, you've found your increasing sequence, so you can stop and say it's true.
If you get to the end of the list without finding a third, bigger number, then you didn't find an increasing sequence, so it's false.

Code Implementation

def increasing_triplet_subsequence(numbers) -> bool:
    smallest_number_seen = float('inf')
    second_smallest_number_seen = float('inf')

    for number in numbers:
        if number <= smallest_number_seen:
            # Found a new smallest number
            smallest_number_seen = number

        elif number <= second_smallest_number_seen:
            # Found a new second smallest number
            second_smallest_number_seen = number

        else:
            # We found a number bigger than
            # both smallest and second smallest
            return True

    # If we didn't find a triplet
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return false immediately since a triplet cannot exist.
Array with fewer than 3 elements	Return false immediately since a triplet cannot exist.
Array with all identical values	The algorithm should correctly return false as no strictly increasing subsequence is possible.
Array sorted in descending order	The algorithm should correctly return false as no strictly increasing subsequence is possible.
Array with a long decreasing sequence followed by increasing elements	The algorithm should eventually find the increasing elements and return true if a triplet is formed.
Array contains very large or very small integers (potential for overflow in naive approaches)	The chosen algorithm should avoid arithmetic operations that could lead to overflow, preferring comparisons.
Array with duplicates interspersed amongst increasing values	The algorithm's logic should handle duplicates correctly, ensuring the subsequence is strictly increasing even with repeated values.
Large array size (scalability considerations)	The algorithm should have a time complexity of O(n) to handle large arrays efficiently; approaches with higher complexity will be less suitable.