Problem of The Day: Maximum Distance in Arrays

Problem Statement

Intuition

When solving this problem, my initial thought was to maximize the distance between the minimum and maximum elements of different arrays. The idea is to identify pairs of elements from different arrays that are as far apart as possible.

Approach

I first flattened the arrays into a single list while keeping track of the original array index for each element. Then, I sorted this flattened list. After sorting, the farthest elements will be at the beginning and the end of this list.

I implemented two pointers to search for the maximum possible distance between elements from different arrays by checking pairs starting from both ends of the sorted list. I did this twice: once scanning from the left and once scanning from the right to ensure I considered all possible pairs.

Complexity

• Time complexity: The time complexity is dominated by the sorting step, which is \(O(N \log N)\), where N is the total number of elements across all arrays.

• Space complexity: The space complexity is \(O(N)\) because I am storing all elements from the arrays in a temporary list.

Code

class Solution:
    def maxDistance(self, arrays: List[List[int]]) -> int:
        temp = []
        for i, array in enumerate(arrays):
            for x in array:
                temp.append([x, i])
        temp.sort()
        l, r = 0, len(temp) - 1
        left, right = 0, 0
        while l < r:
            l_val, l_arr_idx = temp[l]
            r_val, r_arr_idx = temp[r]
            if l_arr_idx != r_arr_idx:
                left = abs(l_val - r_val)
                break
            l += 1
        l, r = 0, len(temp) - 1
        while l < r:
            l_val, l_arr_idx = temp[l]
            r_val, r_arr_idx = temp[r]
            if l_arr_idx != r_arr_idx:
                right = abs(l_val - r_val)
                break
            r -= 1

        return max(left, right)

Editorial

Approach #3 Single Scan [Accepted]

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