We are given a list $L = {(x_1, y_1, z_1), \dots, (x_n, y_n, z_n)}$ and an integer $m \leq n$.
The goal is to find a subset $S \subseteq \{1,\ldots,n\}$ of size $m$ which minimizes the following cost function:
$$\mathit{cost} = \max_{p \in S}(x_p) + \max_{p \in S}(y_p) + \max_{p \in S}(z_p).$$
Is there any subquadratic algorithm to solve the above problem?
This question was recently asked in hiring challenge for an internship in some company. The challenge is over. I have a working solution which runs in $O(n^2 \log{n})$.
Sketch of my algorithm
- Iterate over all points $(x_i, y_i, j_i)$ in non-decreasing order of $x_i$. Along with that maintain a sorted list $S_1$ of pairs $(y_j, z_j)$ such that there is a point $(x_k, y_k, z_k)$ in original list such that $x_k\le x_i$ and $(y_k, z_k)=(y_j, z_j)$. Perform all the following steps in each iteration.
- If $|S_1|<m$ then we know that there can not be any list of $m$ points where maximum value across $x$ coordinate is $x_i$. (In case of multiple point having same $x$-coordinate value we will eventually find a match in next iterations. So no need to worry about it.)
- Now iterate over pairs $(y_j, z_j)$ ($j$ index is not related to one used in second step) in $S_1$ in non-decreasing order of $y_j$. Along with that we maintain another list of $S_2$ of values $z_k$ such that there is some pair $(y_k, z_k) \in S_1$ such that $y_k \le y_j$.
- Now, If $|S_2|\ge m$ then update our $\mathit{ans}$ with $\min(\mathit{ans}, x_i + y_j + m^{th} \text{ largest value in } S_2)$
