<p>You are given <code>m</code> <code>arrays</code>, where each array is sorted in <strong>ascending order</strong>.</p>

<p>You can pick up two integers from two different arrays (each array picks one) and calculate the distance. We define the distance between two integers <code>a</code> and <code>b</code> to be their absolute difference <code>|a - b|</code>.</p>

<p>Return <em>the maximum distance</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arrays = [[1,2,3],[4,5],[1,2,3]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> One way to reach the maximum distance 4 is to pick 1 in the first or third array and pick 5 in the second array.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arrays = [[1],[1]]
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == arrays.length</code></li>
	<li><code>2 &lt;= m &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= arrays[i].length &lt;= 500</code></li>
	<li><code>-10<sup>4</sup> &lt;= arrays[i][j] &lt;= 10<sup>4</sup></code></li>
	<li><code>arrays[i]</code> is sorted in <strong>ascending order</strong>.</li>
	<li>There will be at most <code>10<sup>5</sup></code> integers in all the arrays.</li>
</ul>

class Solution {
public:
    int getMaxDist(vector<int> ar1, vector<int> ar2) {
        int maxDist = 0, dist;
        /*for (int i =0; i<ar1.size();i++) {
            for(int j = 0;j<ar2.size();j++) {
                    if (ar1[i] > ar2[j])
                        dist = ar1[i]-ar2[j];
                    else
                        dist = ar2[j]-ar1[i];

                    if (maxDist < dist) {
                        maxDist = dist;
                    }
            }
        }*/
        /*As the arrays are sorted.... */
        maxDist = abs(ar2[ar2.size()-1]-ar1[0]);
        dist = abs(ar1[ar1.size()-1]-ar2[0]);
        if (maxDist < dist) {
            maxDist = dist;
        }
        
        return maxDist;
    }

    int maxDistance(vector<vector<int>>& arrays) {
        int maxOfMaxDists = 0, maxDist;
        int minN, maxN, minAr, maxAr;
        int pminN, pmaxN, pminAr, pmaxAr;
        if (arrays.size() <=  10) {
            for (int i =0; i<arrays.size(); i++) {
                for (int j=i+1;j<arrays.size();j++) {
                    maxDist = getMaxDist(arrays[i], arrays[j]);
                    if (maxOfMaxDists < maxDist) {
                        maxOfMaxDists = maxDist;
                    }
                }
            }    
            return maxOfMaxDists;  
        }
        
        minN= arrays[0][0];
        maxN = arrays[0][arrays[0].size()-1];
        minAr = 0;maxAr=0;

        pminN= arrays[0][0];
        pmaxN = arrays[0][arrays[0].size()-1];
        pminAr = 0;pmaxAr=0;
        for (int i = 1; i<arrays.size(); i++) {
                if (minN > arrays[i][0]) {
                    pminN = minN;
                    minN = arrays[i][0];
                    pminAr = minAr;
                    minAr = i;
                }

                if (maxN < arrays[i][arrays[i].size()-1]) {
                    pmaxN = maxN;
                    maxN = arrays[i][arrays[i].size()-1];
                    pmaxAr = maxAr;
                    maxAr = i;
                }
        }

        if (minAr != maxAr)
            return abs(maxN-minN);
        int m1 = abs(pmaxN-minN);
        int m2 = abs(maxN-pminN);

        if (m1 > m2)
            return m1;

        return m2;
    }
};
108038