Multi Dimensional Selection

Image placeholder 9899

(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.

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

int: the maximum possible product

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

Get one-to-one training from Google Facebook engineers

Top-notch Professionals

Learn from Facebook and Google senior engineers interviewed 100+ candidates.
Most recent interview questions and system design topics gathered from aonecode alumnus.
One-to-one online classes. Get feedbacks from real interviewers.

Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.
New to the ground? - Develop basic coding skills with your own designated mentor.
Days before interview? - Focus on most important problems in target company question bank.