My way to approach such a problem. How to think about it? Explanation of my think flow.


  • 5
    F

    I initially solved this problem by "thinking hard", so I came up with a convoluted solution (though greatly simplified when coding): https://leetcode.com/discuss/105584/space-time-elegant-short-clean-solution-detailed-explanation

    Today, I revisited this problem. This time, I don't think about how to solve it, instead I want to think about "how to think about it".

    Ok, so I read the description again, then I realize, it is asking about some sort of "increasing subsequence" with size 3.

    Then I think about all the relevant algorithm I know, for example, the famous "Longest Increasing Subsequence" (LIS) problem.

    Then I instantly got a solution: Find the LIS of the input, and if it is greater than 3, return true;
    Looks like a working solution, what's its complexity then:

    There is a O(nlogk) solution to LIS (if you don't know it, just search this problem in Leetcode and see the discussions), where n is the array length and k is the length of LIS. Here, k is no larger than 2, so it is O(nlog2) = O(n). Very well, a O(n) solution is so easily obtained here:

    class Solution {
    public:
        bool increasingTriplet(vector<int>& nums) {
            vector<int> dp;
            for (auto n : nums)
            {
                auto iter = lower_bound(begin(dp), end(dp), n);
                if (iter == end(dp))
                {
                    dp.push_back(n);
                    if (dp.size() == 3)
                        return true;
                    continue;
                }
                if (*iter > n)
                    *iter = n;
            }
            return false;
        }
    };
    

    The only difference between LIS and this problem is the check "if (dp.size() == 3)"; For comparison, this is the code to return the LIS of the input nums: You can copy-paste it to the LIS problem and pass it actually.

    vector<int> dp;
    for (auto n : nums)
    {
        auto iter = lower_bound(begin(dp), end(dp), n);
        if (iter == end(dp))
        {
            dp.push_back(n);
            continue;
        }
        if (*iter > n)
            *iter = n;
    }
    return dp.size();
    

    Apparently, as you may have already noticed, the "dp" here contains at most 2 elements, so one instant simplification here is to replace "lower_bound" call to a simple "if comparison else comparison". Then a much more simplified version is obtained:

    class Solution {
    public:
        bool increasingTriplet(vector<int>& nums) {
            int a = INT_MAX, b = INT_MAX;
            for (auto n : nums)
                if (n <= a)
                    a = n;
                else if (n <= b)
                    b = n;
                else
                    return true;
            return false;
        }
    };
    

    You may have seen 100 ways to explain why this "if .. else" works in other discussions. Here, it is so easy to understand: it is just a simple version of Binary Search for 2 elements -- the replacement of lower_bound in above solution.

    Following this think flow, I managed to come up with this elegant solution without any "hard thinking".


Log in to reply
 

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