Maximum Absolute Pair Sum Across Arrays

Moderate

0/80

0 upvote

Problem statement

You are given K arrays, and each of these arrays is individually sorted in non-decreasing order.

Your task is to select two numbers, x and y, such that x is from one array and y is from a different array, and the value of abs(x + y) is maximized. You need to return this maximum possible value.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer K, the number of arrays.

The next 2*K lines describe the arrays. For each array:
  The first line contains an integer N, the size of the array.
  The second line contains N space-separated integers, the elements of the array.

Output Format:

The output should be a single long integer representing the maximum possible value of abs(x + y).

Note:

The two elements chosen must come from two distinct arrays.

The value to maximize is the absolute value of the sum, abs(x + y). This value will be maximized when x + y is either a very large positive number or a very large (in magnitude) negative number.

Sample Input 1:

Sample Output 1:

Explanation for Sample 1:

To maximize abs(x + y), we consider two cases:
    Maximizing the positive sum: We should pick the two largest positive numbers from different arrays. The largest is 100 (from array 2) and the second largest is 8 (from array 1). Their sum is 100 + 8 = 108.
    Maximizing the negative sum's magnitude: We should pick the two smallest (most negative) numbers from different arrays. The smallest is -20 (from array 1) and the second smallest is -10 (from array 0). Their sum is -20 + -10 = -30.
Comparing the absolute values, abs(108) = 108 and abs(-30) = 30. The maximum is 108.

Expected Time Complexity:

The expected time complexity is O(K), where K is the number of arrays.

Constraints:

2 <= K <= 10^5
1 <= N (size of each array) <= 10^5
The total number of elements across all arrays will not exceed 10^6.
-10^9 <= element value <= 10^9

Approaches (1)

Approach 1

Brute Force

Time Complexity

Space Complexity

(100% EXP penalty)

Maximum Absolute Pair Sum Across Arrays

Console