(This question has been seen in the interviews of the following companies: Tiktok)
Tiktok Online Assessment Questions 2023

Multi Dimensional Selection

Given a 2-d array arr of size n x m, a selection is defined as an array of integers such that it contains at least [m/2] integers from each row of arr. The cost of the selection is defined as the maximum difference between any two integers of the selection.

Suppose k is the minimum cost of all the possible selections for the given 2-d array. Find the maximum value of the product of k * the number of integers considered in the selection with the minimum cost.

Example
Suppose n= 3, m = 2, and arr = [[1, 2], [3, 4], [8, 9]]

Some of the possible selections are [2, 3, 8], [1, 2, 3, 9], [1, 3, 4, 8, 9] etc. The cost of these selections are 8 - 2 = 6, 9 - 1 = 8, and 8 respectively.

Here the minimum cost of all the possible selections is 6. The possible selections with the cost 6 are [2, 4, 8] and [2, 3, 4, 8]. The maximum value of the required product is obtained using the latter selection i.e. 6 * 4 = 24. Hence the answer is 24.

Function Description
Complete the function getMaxProduct in the editor below.

getMaxProduct has the following parameter:
int arr[n][m]: the given 2-d array

Returns
int: the maximum possible product

Constraints
1 <= n <= 10^3
2 <= m <= 10^3
1 <= arr[i][j] <= 10^9