C++ O(N) find min/max and min2/max2


  • 0

    min1 and max1 means the minimum and the maximum number, min2 and max2 means the sub-min and sub-max number.

    class Solution {
    public:
        int maxDistance(vector<vector<int>>& arrays) {
            int min1 = INT_MAX, max1 = INT_MIN, min2 = INT_MAX, max2 = INT_MIN;
            int minIdx = 0, maxIdx = 0;
            for (int i = 0; i < arrays.size(); ++i) {
                int minTmp = arrays[i][0];
                if (minTmp <= min1) min2 = min1, min1 = minTmp, minIdx = i;
                else if (minTmp <= min2) min2 = minTmp;
    
                int maxTmp = arrays[i].back();
                if (maxTmp >= max1) max2 = max1, max1 = maxTmp, maxIdx = i;
                else if (maxTmp >= max2) max2 = maxTmp;
            }
            if (minIdx == maxIdx)
                return std::max(max2 - min1, max1 - min2);
            return max1 - min1;
        }
    };
    

Log in to reply
 

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