algoadvance

Leetcode 334. Increasing Triplet Subsequence

Problem Statement

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. Can the array have duplicate elements?
    • Yes, the array can have duplicate elements, but the requirement is strictly increasing subsequence.
  2. What is the size range for the input array?
    • The input array can vary in size; typically, a size constraint for such LeetCode problems would be up to 10^4.
  3. How should we handle edge cases like empty arrays or arrays with fewer than 3 elements?
    • For arrays with fewer than 3 elements, they are not capable of containing a triplet, so we should return false.

Strategy

To solve this problem, we can utilize a linear scan approach with two auxiliary variables to keep track of the smallest and the second smallest elements encountered so far. This allows us to efficiently determine the presence of such an increasing triplet subsequence.

  1. Initialize two variables first and second with the maximum possible integer value.
  2. Iterate through the array:
    • If the current element is less than or equal to first, update first to the current element.
    • Else if the current element is less than or equal to second, update second to the current element.
    • Otherwise, we have found a valid increasing triplet subsequence and can return true.
  3. If we complete the loop without finding such a triplet, return false.

Code

#include <vector>
#include <limits.h>

bool increasingTriplet(std::vector<int>& nums) {
    int first = INT_MAX, second = INT_MAX;
    for (int num : nums) {
        if (num <= first) {
            first = num;
        } else if (num <= second) {
            second = num;
        } else {
            return true;
        }
    }
    return false;
}

Time Complexity

The algorithm runs in O(n) time where n is the size of the input array, as it involves a single pass through the array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI