Maximum Distance in Arrays(From Intuition to the Optimized Code:

Intuition:

Intuition behind this problem is to first find all the pairs such that we got maximum absolute difference, But in question it is mentioned that m arrayLists are sorted, So can we think or go with Greedy though process ? Greedy I mean, Just take last element and first element from each List and find absolute difference. ? what do you think ? Let's Go with this Approach.

Approach:

steps:
s-1 Assume min as first element which is present at the 0th idx of the first ArrayList within the outer ArrayList.
s-2 Similarly, Assume max as last element which is present at the last idx of the first ArrayList within the outer ArrayList.
s-3 Iterate over the Outer ArrayList from next idx i.e. idx = 1.
s-4 Now find currMin element form curr idx List and find currMax element from curr idx List.
s-5 As according to the question, We don't take minimum and maximum element from the same List(Internal List) So, we just find the absolute difference by subtracting currMin from max and find the absolute difference by subtracting currMax from min. i.e.
Math.abs(max - currMin) and Math.abs(min - currMax)
s-6 find the maximum absolute difference from these two pairs.
s-7 Continuously find maximum absolute difference to cover the all the possible pairs till the last idx of Outer List.
s-8 In each Iteration Update your max as Max of (max , currMax) and Update your min as Min of (min, currMin).

Complexity:

• Time complexity:

• O(m)

• Space complexity: O(1)

JAVA Code:

class Solution {
    public int maxDistance(List<List<Integer>> arrays) {
        int min = arrays.get(0).get(0);
        int max = arrays.get(0).get(arrays.get(0).size() -1);
        int result = 0;
        for(int i =1; i < arrays.size(); i++){
            int currMin = arrays.get(i).get(0);
            int currMax = arrays.get(i).get(arrays.get(i).size() -1);
            result = Math.max(result, Math.max(Math.abs(currMin - max), Math.abs(currMax - min)));
            max = Math.max(max, currMax);
            min = Math.min(min, currMin);
        }
        return result;
    }
}