Clean and short, with comments, C++


  • 148
    A
    bool increasingTriplet(vector<int>& nums) {
        int c1 = INT_MAX, c2 = INT_MAX;
        for (int x : nums) {
            if (x <= c1) {
                c1 = x;           // c1 is min seen so far (it's a candidate for 1st element)
            } else if (x <= c2) { // here when x > c1, i.e. x might be either c2 or c3
                c2 = x;           // x is better than the current c2, store it
            } else {              // here when we have/had c1 < c2 already and x > c2
                return true;      // the increasing subsequence of 3 elements exists
            }
        }
        return false;
    }

  • 0
    M
    This post is deleted!

  • 0
    C

    very neat and brilliant solution!


  • 7

    Your solution is just to keep a window of size=3, and keep updating the c1 and c2 just like the LIS(longest increasing sequence) Problem. but we know the size=3, so we need do not need to use the binary search to find the updating position, so we can do it in O(N).
    You can see me LIS solution in

    https://leetcode.com/discuss/87255/just-using-the-lis-to-solve-the-problem-in-8ms


  • 0
    V

    The approach is simple: Continuously update the range covered by 2 numbers represented by A[0] & A[1]. Initially they are initialized by INT_MAX and we keep lowering their values. If anytime we find a number larger than A[1], return true.

    class Solution {
    public:
        bool increasingTriplet(vector<int>& x) {
            int A[2] = {INT_MAX, INT_MAX};
            if (x.size() < 3)
                return false;
            for (int i = 0; i < x.size(); i++) {
                if (x[i] < A[0])
                    A[0] = x[i];
                else if (x[i] > A[0] && x[i] < A[1])
                    A[1] = x[i];
                else if (x[i] > A[1] && x[i] <= INT_MAX)
                    return true;
                else
                    continue;
            }
            return false;
        }
    };

  • 0
    A
    This post is deleted!

  • 0
    Z
    class Solution {
    public:
        bool increasingTriplet(vector<int>& nums) {
        int len=nums.size();
        int a[3];
        int pos=-1;
        for(int i=0;i<len;i++) {
            if(pos==-1||nums[i]>a[pos]) {
                a[++pos]=nums[i];
                if(pos==2) return true;
            }
            else {
                if(nums[i]<a[0]) 
                    a[0]=nums[i];
                else if(pos==1&&nums[i]>a[0]&&nums[i]<a[1]) 
                    a[1]=nums[i];
            }
        }
        return false;
        }
    };

  • 0
    B

    it is not work. It will always stuck at first if condition.


  • 0
    L

    Very smart solution, thank you!


  • 32
    O

    before coding I also thought about this solution and I did’t think that will work, as it appears to be very naïve and greedy: find first smallest, then find second smallest, then find the third and bingo. I argued myself it cannot pass the case like [1,2,0,3] since c1 is changed.

    But when I take a closer look, it does [1,2,0,3] very well. And I realize that c1 and c2 are indeed having the meaning of:

    C1 = so far best candidate of end element of a one-cell subsequence to form a triplet subsequence

    C2 = so far best candidate of end element of a two-cell subsequence to form a triplet subsequence

    So c1 and c2 are the perfect summary of history.

    public class Solution {
        public boolean increasingTriplet(int[] nums) {
            int c1 = Integer.MAX_VALUE, c2 = Integer.MAX_VALUE;
            for (int i : nums) 
                if (i <= c1)
                    c1 = i;
                else if (i <= c2)
                    c2 = i;
                else
                    return true;
            return false;
        }
    }
    

  • -1
    I

    I feel like your algorithm wouldn't work for this case:
    [-10, 1, 2, 3, -7]


  • 0

    Your words are the key ideas ! Good summary !


  • 0

    If you use three variables to represent the dp table, you will find these two approaches are exactly the same.


  • 0

    What you summarized are actually exactly the same rules to find LIS. Just because the conditions can be simplified to several lines, you think the posted method is a naive sliding window method.


  • 0
    O

    @jedihy, I don't think the posted method is naive. You are right, its the same method as in LIS.


  • 0
    O

    @RainbowSecret This view is very great! Thanks!


  • -3
    H

    It uses O(2) space complexity -> c1 & c2. The Q says, use O(1) space.


  • 1
    A

    @horizon When we say O(1) space, we actually mean O(constant) space


  • 0

    Explanation

    if      (x <= a) a = x; // a = min so far
    else if (x <= b) b = x; // b = min element **with a smaller element to the left**
    else    return true;    // x > b, we found an answer
    

  • 1

    @alveko FYI - wow the simplicity of this approach is awesome!

    I came up with this, which is way less awesome but more how you might try it by hand (which is how I stumbled into it's trap!).

    As you iterate your array you want to keep the "best" increasing pair, which is the pair with the lowest top value. Of course if you find a value above the top of your pair you're done, a value between the pair you just update the top end. Now if the value is less than your low end you need to hold it until you find another also lower than your low end but above this held value. Once you find this you have a new "best" pair.

    Of course when you go to code this it does not look so pretty and of course is not nearly as slick as when you just realize you can get away with only keeping the last 2.

    One advantage I would say though is that if you needed to actually produce the indexes for the triplet you would actually need something like below.

    Thanks!

    public class Solution 
    {
        public bool IncreasingTriplet(int[] nums) 
        {
            Doublet doublet = new Doublet();
            for (int i = 0; i < nums.Length; i++)
            {
                if (doublet.Check(nums, i)) return true;
            }
            
            return false;
        }
    }
    
    public class Doublet
    {
        public int index1 = -1;
        public int index2 = -1;
        public int indexNext = -1;
        
        public bool Check(int[] arr, int i)
        {
            if (index1 != -1 && index2 != -1 && arr[i] > arr[index2])
            {
                // found
                return true; 
            }
            
            if (index1 == -1 || (arr[i] <= arr[index1] && index2 == -1))
            {
                // new 1
                index1 = i; 
            }
            else if (index2 == -1 || (arr[i] > arr[index1] && arr[i] < arr[index2]))
            {
                // new 2
                index2 = i; 
            }
            else if (arr[i] < arr[index1]) 
            {
                if (indexNext == -1 || arr[i] < arr[indexNext])
                {
                    // new overall min - hold
                    indexNext = i;
                }
                else if (arr[i] > arr[indexNext] && arr[i] <= arr[index1])
                {
                    // new pair - promote
                    index2 = i;
                    index1 = indexNext;
                    indexNext = -1;
                }
            }
            
            // not found
            return false;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.