Likely the fastest at this moment C++ solution


  • 0
    A

    Hello! The code is below. It runs on Leetcode in 29ms. They did not show any chart so I made my own test, which measures the time to execute and skips the time to build the data for the test. The time is measured between the printing statements in the test code below.

    My test runs in 2.4 sec. Other C++ solutions I tried with my test are:

    https://discuss.leetcode.com/topic/92858/c-o-n
    https://discuss.leetcode.com/topic/92888/c-o-n-find-min-max-and-min2-max2
    https://discuss.leetcode.com/topic/92875/c-solution

    They all run longer than 4 seconds. The last one https://discuss.leetcode.com/topic/92875/c- is pretty good. It runs my test in 2.7 if that anitOptimizer2 vector is not "bad case". If it is "bad case" as I have provided its execution time doubles.

    With Visual Studio 2017 I make the Process method a private static member of the class. This is better because its semantic is reasonable only in context of inner logic of the algorithm. LeetCode's C++ compiler could not stand it so I had to extract it out.

    The role of antiOptimizer variables is to force the code to compute. VS C++ compiler is pretty smart and completely eliminates the code if it sees that its results are not used at all or when it sees that the results do not change with the next calls and the previous computations can be reused.

    Code:

    // Helper method to find the 2 minimum or 2 maximum elements of a sequence.
    // The decition is based on Less specialization.
    // Each pair describes the index of the array and a value from it.
    // Comparison is made only for value. The index is for tracking.
    template <class Less>
    void Process(const pair<size_t, int>& p, pair<size_t, int>& p1, pair<size_t, int>& p2, const Less& less)
    {
    	if (less(p.second, p1.second))
    	{
    		p2 = p1;
    		p1 = p;
    	}
    	else if (less(p.second, p2.second))
    	{
    		p2 = p;
    	}
    }
    
    
    class Solution
    {
    public:
    	int maxDistance(const vector<vector<int>>& arrays) const
    	{
    		pair<size_t, int> p1(0, arrays[0].front());
    		pair<size_t, int> p2(1, arrays[1].front());
    
    		pair<size_t, int> p3(0, arrays[0].back());
    		pair<size_t, int> p4(1, arrays[1].back());
    
    		if (p2.second < p1.second)
    			swap(p1, p2);
    
    		if (p3.second < p4.second)
    			swap(p3, p4);
    
    		for (size_t i = 2, n = arrays.size(); i < n; ++i)
    		{
    			Process(make_pair(i, arrays[i].front()), /*ref*/ p1, /*ref*/ p2, [](const int& l, const int& r) { return l < r; });
    			Process(make_pair(i, arrays[i].back()), /*ref*/ p3, /*ref*/ p4, [](const int& l, const int& r) { return r < l; });
    		}
    
    		int r = numeric_limits<int>::min();
    
    		if (p1.first != p3.first)
    			r = max(r, abs(p3.second - p1.second));
    
    		if (p1.first != p4.first)
    			r = max(r, abs(p4.second - p1.second));
    
    		if (p2.first != p3.first)
    			r = max(r, abs(p3.second - p2.second));
    
    		if (p2.first != p4.first)
    			r = max(r, abs(p4.second - p2.second));
    
    		return r;
    	}
    };
    

    Test

            const size_t N = 10000;
    	vector<vector<int>> bigArr(N);
    	for (size_t i = 0; i < N; ++i)
    	{
    		size_t k = rand() + 1;
    		vector<int> arr(k);
    		for (size_t j = 0; j < k; ++j)
    			arr[j] = rand();
    
    		sort(arr.begin(), arr.end());
    		bigArr[i] = move(arr);
    	}
    
    puts("Starting");
    
    	int antiOptimizer = 0;
    	vector<int> antiOptimizer2 = { -50000, 50000 };
    	// vector<int> antiOptimizer2 = { 0, 1};
    	for (size_t iter = 0; iter < 10000; ++iter)
    	{
    		bigArr.push_back(antiOptimizer2);
    		antiOptimizer += s.maxDistance(bigArr);
    		bigArr.pop_back();
    	}
    
    	printf("Done %d\n", antiOptimizer);
    

Log in to reply
 

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