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

    Webmaster (Zhang Jian): πŸ‘‹

    Hi everyone! I am Zhang Jian.
    I know the challenge of transitioning from mastering algorithms to actually landing a great job. That's why, in addition to this resource, I personally developed leader.me!

    πŸš€ leader.me is the ultimate all-in-one platform for programmers to build their personal brand, featuring portfolio hosting, resume builders, and integrated blogs.

    Build your programmer brand at leader.me β†’


    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, then triplet found β†’ return true.
      • else (current element < second)
        • 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

            # Here, nums[i] <= second
            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;
            }

            // Here, nums[i] <= second
            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;
            }

            // Here, nums[i] <= second
            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
    }

    // Here, nums[i] <= second
    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;
            }

            // Here, nums[i] <= second
            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
        }

        // Here, num <= second
        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  

    # Here, num <= second
    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.blog GitHub -> 334. Increasing Triplet Subsequence. Thanks!
    PreviousNext

    Level Up Your Developer Identity

    πŸš€ While mastering algorithms is key, showcasing your talent is what gets you hired.
    We recommend leader.me β€” the ultimate all-in-one personal branding platform for programmers.

    The All-In-One Career Powerhouse:

    • πŸ“„ Resume, Portfolio & Blog: Integrate your skills, projects, and writing into one stunning site.
    • 🌐 Free Custom Domain: Bind your own personal domain for freeβ€”forever.
    • ✨ Premium Subdomains: Stand out with elite tech handle like name.leader.me.

    Build Your Programmer Brand at leader.me β†’