LeetCode Python/Java/C++/JS  >  Greedy Algorithm  >  334. Increasing Triplet Subsequence  >  Solved in Python, Java, C++, JavaScript, C#, Go, Ruby  >  GitHub or Repost

    LeetCode link: 334. Increasing Triplet Subsequence, difficulty: Medium.

    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^5
    • -2^31 <= nums[i] <= 2^31 - 1

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

    Intuition
    PreviousNext

    To find an increasing triplet subsequence, we can track the smallest and second-smallest elements seen so far. If we encounter an element larger than both, we've found our triplet.

    Pattern of "Greedy Algorithm"

    The Greedy Algorithm is a strategy that makes the locally optimal choice at each step with the hope of leading to a "globally optimal" solution. In other words, "local optima" can result in "global optima."

    Step-by-Step Solution

    1. Initialize first as the first element and second as infinity.
    2. Iterate through the array starting from the second element:
      • If current element > second, triplet found → return true.
      • If current element > first, update second to current element.
      • Else, update first to current element (keeping it the smallest seen so far).
    3. If loop completes without finding a triplet, return false.

    Complexity

    Time complexity

    O(N)

    Space complexity

    O(1)

    Solution in languages: Python Java C++ JavaScript C# Go Ruby

    Python # 

    class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        first = nums[0]
        second = float('inf')

        for i in range(1, len(nums)):
            if nums[i] > second:
                return True

            if nums[i] > first:
                second = nums[i]
            else:
                first = nums[i]

        return False

    Java # 

    class Solution {
    public boolean increasingTriplet(int[] nums) {
        int first = nums[0];
        int second = Integer.MAX_VALUE;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > second) {
                return true;
            }

            if (nums[i] > first) {
                second = nums[i];
            } else {
                first = nums[i];
            }
        }
        return false;
    }
}

    C++ # 

    class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int first = nums[0];
        int second = INT_MAX;

        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > second) {
                return true;
            }

            if (nums[i] > first) {
                second = nums[i];
            } else {
                first = nums[i];
            }
        }

        return false;
    }
};

    JavaScript # 

    /**
 * @param {number[]} nums
 * @return {boolean}
 */
var increasingTriplet = function (nums) {
  let first = nums[0]
  let second = Infinity

  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > second) {
      return true
    }

    if (nums[i] > first) {
      second = nums[i]
    } else {
      first = nums[i]
    }
  }

  return false
};

    C# # 

    public class Solution {
    public bool IncreasingTriplet(int[] nums) {
        int first = nums[0];
        int second = int.MaxValue;

        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] > second) {
                return true;
            }

            if (nums[i] > first) {
                second = nums[i];
            } else {
                first = nums[i];
            }
        }

        return false;
    }
}

    Go # 

    func increasingTriplet(nums []int) bool {
    first := nums[0]
    second := math.MaxInt32

    for _, num := range nums[1:] {
        if num > second {
            return true
        }

        if num > first {
            second = num
        } else {
            first = num
        }
    }

    return false
}

    Ruby # 

    # @param {Integer[]} nums
# @return {Boolean}
def increasing_triplet(nums)
  first = nums[0]
  second = Float::INFINITY

  nums[1..].each do |num|
    if num > second
      return true
    end  

    if num > first
      second = num
    else
      first = num
    end
  end

  false
end
    Solution in languages: Python Java C++ JavaScript C# Go Ruby

    Other languages

    Welcome to contribute code to LeetCode.to GitHub -> 334. Increasing Triplet Subsequence. Thanks!
    PreviousNext