Saturday, November 26, 2016

LeetCode OJ - 132 Pattern

Problem:

Please find the problem here.

Solution: 

We have to have a linear algorithm because the given size is very large (n < 15000).

Note that it is relatively easy to break the sequence into increasing/decreasing ranges, so we can think of the sequence as an alternating sequence of  increasing/decreasing ranges.

If there exists a 132 pattern, the 13 part must be in an increasing range, and the 2 must be somewhere else after that increasing range, so we can always make the 1 the start of the increasing range, and 3 as the end of the increasing range. So we have all the candidate 13 parts by a single scan.

The real problem is finding a 2. If we find out all the increasing range and then find the 2, we will be screwed by the quadratic performance because there could be $ O(n) $ increasing ranges and every search take $ O(n) $ time.

The key idea is that suppose we have an increasing range $ [a, b] $ and the next value is $ c $, $ c $ must be less than $ b $ otherwise the increasing range simply continues. If $ a < c < b $ then we are done finding the 132 pattern, so the worst case we need to cater is $ c < a $.

Therefore, the current set of increasing ranges should be sorted by their starting point in descending order, now whenever we find a number $ a < d < b $, we can declare we are done, otherwise for $ d < a $ we continue building up the increasing range, or when $ b \le d $ we can forget about the range $ [a, b] $ because we have a better range $ [c, d] $. We can simply manage these increasing ranges in a stack!

Analysis:

But why is this new algorithm better than just search? The key idea is that a range is either checked once per number and done (either because $ d < a $ or $ a < d < b $) or it is popped away ($ b \le d $). Imagine we are investing coins. For each number, we spend one coin to check for a range in the stack. And whenever we create a range, we invest one coin in our saving account. It can be easily seen that with some careful arrangement we can always invest only constant amount of coin per number, therefore the overall performance is $ O(n) $.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/132-pattern/

#include "LEET_132_PATTERN.h"
#include <stack>
#include <map>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_132_PATTERN
{
    class Solution
    {
    public:
        bool find132pattern(vector<int>& nums)
        {
            if (nums.size() < 3)
            {
                return false;
            }
            stack<pair<int, int>> increasing_ranges;
            int range_begin = -1;
            int state = 1;
            for (int i = 0; i < nums.size(); i++)
            {
                while (increasing_ranges.size() > 0)
                {
                    pair<int, int> top = increasing_ranges.top();
                    if (nums[i] > top.first && nums[i] < top.second)
                    {
                        return true;
                    }
                    else if (nums[i] >= top.second)
                    {
                        increasing_ranges.pop();
                    }
                    else
                    {
                        break;
                    }
                }
                if (i < nums.size() - 1)
                {
                    if (state == 1)
                    {
                        if (nums[i] < nums[i + 1])
                        {
                            range_begin = nums[i];
                            state = 2;
                        }
                        // otherwise stay in state 1
                    }
                    else
                    {
                        // state == 2
                        if (nums[i] > nums[i + 1])
                        {
                            // we have found an increasing range
                            increasing_ranges.push(pair<int, int>(range_begin, nums[i]));
                            state = 1;
                        }
                        // otherwise stay in state 2
                    }
                }
            }
            return false;
        }
    };
};

using namespace _LEET_132_PATTERN;

int LEET_132_PATTERN()
{
    Solution solution;
    int input1[] = { 1, 2, 3, 4 };
    int input2[] = { 3, 1, 4, 2 };
    int input3[] = { -1, 3, 2, 0 };
    int input4[] = { 1,0,1,-4,-3 };
    int input5[] = { 8, 10, 4, 6, 5 };
    cout << solution.find132pattern(vector<int>(input1, input1 + _countof(input1))) << endl;
    cout << solution.find132pattern(vector<int>(input2, input2 + _countof(input2))) << endl;
    cout << solution.find132pattern(vector<int>(input3, input3 + _countof(input3))) << endl;
    cout << solution.find132pattern(vector<int>(input4, input4 + _countof(input4))) << endl;
    cout << solution.find132pattern(vector<int>(input5, input5 + _countof(input5))) << endl;
    return 0;
}

No comments :

Post a Comment