Jobs

Interviews

Discussions

Increasing Triplet Subsequence

Medium

Apple

2 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.

For example:

nums = [1,2,3,4,5] Output: true Explanation: Any triplet where i < j < k is valid.
nums = [5,4,3,2,1] Output: false Explanation: No triplet exists.
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.

Could you provide an efficient algorithm to solve this problem, considering the constraints 1 <= nums.length <= 5 * 10^5 and -2^31 <= nums[i] <= 2^31 - 1? Ideally, aim for a solution with O(n) time complexity and O(1) space complexity.

Increasing Triplet Subsequence

Medium

Apple

2 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.

For example:

nums = [1,2,3,4,5] Output: true Explanation: Any triplet where i < j < k is valid.
nums = [5,4,3,2,1] Output: false Explanation: No triplet exists.
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

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 range of values within the `nums` array? Can I expect negative numbers, zero, or only positive integers?
Can the input array `nums` be empty or null? If so, what should I return?
Are duplicate values allowed in the array, and if so, does `nums[i] < nums[j] < nums[k]` imply that the values at those indices must be distinct, or just non-decreasing?
If multiple increasing triplets exist, do I need to return all of them, or is it sufficient to return `true` as soon as the first one is found?
What is the maximum size of the input array `nums`? This will help me consider space complexity implications.

Brute Force Solution

Approach

The brute force approach to finding an increasing triplet involves examining every possible combination of three numbers in the given set. We're essentially checking each possible triplet to see if it fits the increasing order requirement. If we find one, we're done.

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

Pick the first number from the set.
For each first number, pick a second number that comes after it in the set.
For each pair of first and second numbers, pick a third number that comes after the second number in the set.
Check if the first number is smaller than the second number AND the second number is smaller than the third number.
If both conditions are true, you've found an increasing triplet; stop and indicate that one exists.
If you've tried all possible combinations of three numbers and haven't found a valid triplet, then no increasing triplet exists in the set.

Code Implementation

def increasing_triplet_subsequence_brute_force(numbers):
    list_length = len(numbers)
    for first_index in range(list_length):

        # Iterate through the rest of the list
        for second_index in range(first_index + 1, list_length):

            #The second number must be larger than the first
            if numbers[first_index] < numbers[second_index]:

                for third_index in range(second_index + 1, list_length):

                    #The third number must be larger than the second
                    if numbers[second_index] < numbers[third_index]:
                        return True

    # No increasing triplet was found
    return False

Big(O) Analysis

Time Complexity

O(n³) – The brute force approach iterates through all possible triplets in the input array of size n. The outer loop picks the first element. The nested loop picks the second element after the first. The innermost loop picks the third element after the second. Therefore, we have three nested loops, resulting in approximately n * n * n operations which simplifies to O(n³).

Space Complexity

O(1) – The brute force approach, as described, does not utilize any auxiliary data structures like lists, hash maps, or sets. It only involves iterating through the input array and using a few variables for comparisons and tracking indices of the potential triplet. Therefore, the amount of extra memory used remains constant regardless of the input size N, where N is the number of elements in the input array. This constant space usage translates to O(1) space complexity.

Optimal Solution

Approach

The key idea is to efficiently track the smallest and second smallest numbers seen so far. We look for a number that is larger than both of these, which signifies an increasing triplet exists, thus avoiding unnecessary comparisons.

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

Keep track of the smallest number you've seen so far. Initialize it to a very large value.
Keep track of the second smallest number you've seen so far. Initialize it to a very large value.
Go through the numbers one by one.
If the current number is smaller than the smallest number, update the smallest number.
Otherwise, if the current number is smaller than the second smallest number, update the second smallest number.
Otherwise, if the current number is greater than both the smallest and second smallest number, you've found an increasing triplet, and you're done.
If you go through all the numbers and haven't found a triplet, it doesn't exist.

Code Implementation

def increasing_triplet_subsequence(numbers):
    smallest_number = float('inf')
    second_smallest_number = float('inf')

    for current_number in numbers:
        if current_number <= smallest_number:
            # Update smallest if current is smaller.
            smallest_number = current_number

        elif current_number <= second_smallest_number:
            # Update second smallest if current is smaller.
            second_smallest_number = current_number

        else:
            # Found a number > smallest and second smallest.
            return True

    return False

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array nums of size n only once. Inside the loop, it performs a constant number of comparisons and updates of min1 and min2. Therefore, the dominant factor determining the runtime is the single pass through the array, resulting in a time complexity of O(n).

Space Complexity

O(1) – The algorithm uses only two variables, smallest and second_smallest, to keep track of the smallest and second smallest numbers seen so far. The space required for these variables does not depend on the size of the input array, N. Therefore, the auxiliary space complexity is constant, which is O(1).

Edge Cases

Case	How to Handle
Empty or null input array	Return false immediately, as a subsequence of length 3 cannot exist.
Array with fewer than 3 elements	Return false because an increasing subsequence of length 3 requires at least 3 elements.
Array with all identical elements	The solution should return false as no strictly increasing subsequence is possible.
Array sorted in descending order	The solution should return false as no increasing subsequence is possible.
Array with maximum-sized input containing integers at the maximum/minimum limit of the integer range.	The solution should still function correctly without integer overflow concerns in comparison operations.
Array containing duplicate elements interspersed amongst possible solution	The solution should correctly identify if an increasing subsequence exists despite the duplicates.
Array contains negative numbers	The solution should handle negative numbers correctly in comparison operations.
Array where the increasing triplet is located at the very end of the array	The algorithm needs to iterate through the entire array to identify the increasing triplet even if it is at the end.

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 range of values within the `nums` array? Can I expect negative numbers, zero, or only positive integers?
Can the input array `nums` be empty or null? If so, what should I return?
Are duplicate values allowed in the array, and if so, does `nums[i] < nums[j] < nums[k]` imply that the values at those indices must be distinct, or just non-decreasing?
If multiple increasing triplets exist, do I need to return all of them, or is it sufficient to return `true` as soon as the first one is found?
What is the maximum size of the input array `nums`? This will help me consider space complexity implications.

Brute Force Solution

Approach

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

Pick the first number from the set.
For each first number, pick a second number that comes after it in the set.
For each pair of first and second numbers, pick a third number that comes after the second number in the set.
Check if the first number is smaller than the second number AND the second number is smaller than the third number.
If both conditions are true, you've found an increasing triplet; stop and indicate that one exists.
If you've tried all possible combinations of three numbers and haven't found a valid triplet, then no increasing triplet exists in the set.

Code Implementation

def increasing_triplet_subsequence_brute_force(numbers):
    list_length = len(numbers)
    for first_index in range(list_length):

        # Iterate through the rest of the list
        for second_index in range(first_index + 1, list_length):

            #The second number must be larger than the first
            if numbers[first_index] < numbers[second_index]:

                for third_index in range(second_index + 1, list_length):

                    #The third number must be larger than the second
                    if numbers[second_index] < numbers[third_index]:
                        return True

    # No increasing triplet was found
    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 so far. Initialize it to a very large value.
Keep track of the second smallest number you've seen so far. Initialize it to a very large value.
Go through the numbers one by one.
If the current number is smaller than the smallest number, update the smallest number.
Otherwise, if the current number is smaller than the second smallest number, update the second smallest number.
Otherwise, if the current number is greater than both the smallest and second smallest number, you've found an increasing triplet, and you're done.
If you go through all the numbers and haven't found a triplet, it doesn't exist.

Code Implementation

def increasing_triplet_subsequence(numbers):
    smallest_number = float('inf')
    second_smallest_number = float('inf')

    for current_number in numbers:
        if current_number <= smallest_number:
            # Update smallest if current is smaller.
            smallest_number = current_number

        elif current_number <= second_smallest_number:
            # Update second smallest if current is smaller.
            second_smallest_number = current_number

        else:
            # Found a number > smallest and second smallest.
            return True

    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return false immediately, as a subsequence of length 3 cannot exist.
Array with fewer than 3 elements	Return false because an increasing subsequence of length 3 requires at least 3 elements.
Array with all identical elements	The solution should return false as no strictly increasing subsequence is possible.
Array sorted in descending order	The solution should return false as no increasing subsequence is possible.
Array with maximum-sized input containing integers at the maximum/minimum limit of the integer range.	The solution should still function correctly without integer overflow concerns in comparison operations.
Array containing duplicate elements interspersed amongst possible solution	The solution should correctly identify if an increasing subsequence exists despite the duplicates.
Array contains negative numbers	The solution should handle negative numbers correctly in comparison operations.
Array where the increasing triplet is located at the very end of the array	The algorithm needs to iterate through the entire array to identify the increasing triplet even if it is at the end.