Problem

You are given m arrays, where each array is sorted in ascending order.

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 a and b to be their absolute difference |a - b|.

Return the maximum distance.

Examples

Example 1:

Input: arrays =[[1,2,3],[4,5],[1,2,3]]
Output: 4
Explanation: 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.

Example 2:

Input: arrays =[[1],[1]]
Output: 0

Solution

Solution

This solution can be solved by using greedy paradigm. Please find the video explanation below:

Method 1 - Min and Max Difference

Here are the steps we can take:

  1. Understand the formula:
    • The distance between two integers (a) and (b) from two different arrays is (|a - b|).
  2. Leverage Sorted Property:
    • Since each array is sorted in ascending order, the smallest number from an array is the first element, and the largest number is the last element.
  3. Track Min and Max Values across Arrays:
    • As we iterate through each array, we keep track of the global minimum value and the global maximum value so far.
    • We also compute and update the maximum distance by comparing the first element of the current array with the global maximum value encountered so far and the last element of the current array with the global minimum value encountered so far.
    • Update the global minimum and global maximum values accordingly.

Code

Java
public class Solution {
    public int maxDistance(List<List<Integer>> arrays) {
        int minVal = arrays.get(0).get(0);
        int maxVal = arrays.get(0).get(arrays.get(0).size() - 1);
        int maxDist = 0;

        for (int i = 1; i < arrays.size(); i++) {
            List<Integer> currArr = arrays.get(i);
            int currMin = currArr.get(0);
            int currMax = currArr.get(currArr.size() - 1);

            maxDist = Math.max(maxDist, Math.abs(currMax - minVal));
            maxDist = Math.max(maxDist, Math.abs(maxVal - currMin));

            // Update the global minimum and maximum values
            minVal = Math.min(minVal, currMin);
            maxVal = Math.max(maxVal, currMax);
        }

        return maxDist;
    }
}

Complexity

  • ⏰ Time complexity: O(m) where m is number of arrays, as we pass through each array exactly once, that too checking only min and max values.
  • 🧺 Space complexity: O(1)

Method 2 - Calculating Global and Second maxima and minima

We can use a slightly different approach by finding the global minimum and maximum values among different arrays and handle the cases when the minimum and maximum values come from the same array by comparing with the second minimum and second maximum values from other arrays. Here’s the detailed approach:

Approach:

  1. Identify Global Min and Max:
    • First, find the overall minimum and maximum values and their respective array indices.
  2. Handle Same Array Case:
    • If the global minimum and maximum are from the same array, find the second minimum and second maximum by ignoring elements from this array.
    • Compute distances between the pairs of values (min and second max, max and second min).
  3. Return the Largest Distance:
    • The answer will be the maximum of these computed distances.

Code

Java

public class Solution {
    public int maxDistance(List<List<Integer>> arrays) {
        // Variables to track global min and max and their indices
        int globalMin = Integer.MAX_VALUE;
        int minIndex = -1;
        int globalMax = Integer.MIN_VALUE;
        int maxIndex = -1;

        // First pass to find global min and max
        for (int i = 0; i < arrays.size(); i++) {
            int currentMin = arrays.get(i).get(0);
            int currentMax = arrays.get(i).get(arrays.get(i).size() - 1);
            if (currentMin < globalMin) {
                globalMin = currentMin;
                minIndex = i;
            }
            if (currentMax > globalMax) {
                globalMax = currentMax;
                maxIndex = i;
            }
        }

        // If global min and max are from different arrays, return the distance
        if (minIndex != maxIndex) {
            return globalMax - globalMin;
        }

        // Variables to track the second min and max
        int secondMin = Integer.MAX_VALUE;
        int secondMax = Integer.MIN_VALUE;

        // Second pass to find second min and max for the same-index case
        for (int i = 0; i < arrays.size(); i++) {
            if (i != minIndex) {
                int currentMin = arrays.get(i).get(0);
                int currentMax = arrays.get(i).get(arrays.get(i).size() - 1);
                if (currentMin < secondMin) {
                    secondMin = currentMin;
                }
                if (currentMax > secondMax) {
                    secondMax = currentMax;
                }
            }
        }

        // Calculate possible maximum distances
        int maxDist1 = globalMax - secondMin;
        int maxDist2 = secondMax - globalMin;

        // Return the maximum of the two computed distances
        return Math.max(maxDist1, maxDist2);
    }

}

Complexity

  • ⏰ Time complexity: O(m)
  • 🧺 Space complexity: O(1)