Maximum Distance in Arrays

Leetcode Problem:

• Maximum Distance in Arrays

Summary

• Finding the maximum distance between two numbers from different sorted arrays.

Approach

• This solution uses two pointers to track the minimum and maximum values from each array
• It keeps track of the indices and values of these numbers to find the maximum distance.

Complexity

• O(m * log(m)) due to sorting the arrays, where m is the number of arrays.

Explain

• The solution first initializes variables to store the minimum and maximum values from each array
• It then iterates through each array to find the minimum and maximum values
• After finding these values, it checks if the maximum and minimum values are from the same array or different arrays
• If they are from the same array, it calculates the distance between them
• If they are from different arrays, it calculates the distance between the maximum value and the minimum value from the same array, and the distance between the maximum value and the minimum value from the other array
• It then returns the maximum of these distances.

Solution Code:

struct number{
    int idx;
    int value;
};
class Solution {
public:
    int ABS(int x){
        return x < 0 ? -x: x;
    }
    int maxDistance(vector>& arrays) {
        number minNum = {0, 10001};
        number secondMinNum = {0, 10001};

        number maxNum = {0, -10001};
        number secondMaxNum = {0, -10001};

        for(int i = 0 ; i < arrays.size(); i++){
            int minValue = arrays[i][0];
            int maxValue = arrays[i][arrays[i].size() - 1];
            if (minValue 
                secondMinNum.value = minNum.value;
                secondMinNum.idx = minNum.idx;
                minNum.value = minValue;
                minNum.idx = i;
            } else if (minValue < secondMinNum.value){
                secondMinNum.value = minValue;
                secondMinNum.idx = i;
            }

            if (maxValue > maxNum.value){
                secondMaxNum.value = maxNum.value;
                secondMaxNum.idx = maxNum.idx;
                maxNum.value = maxValue;
                maxNum.idx = i;
            } else if (maxValue > secondMaxNum.value){
                secondMaxNum.value = maxValue;
                secondMaxNum.idx = i;
            }
        }
        if (maxNum.idx != minNum.idx){
            return ABS(maxNum.value - minNum.value);
        } else{
            int a = ABS(maxNum.value - secondMinNum.value);
            int b = ABS(secondMaxNum.value - minNum.value);
            return a > b ? a : b;
        }

    }
};