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)$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.