Help with a problem asked in a recent CodingNinjas test

Revision en1, by t0rto1se, 2022-07-29 20:20:20

Problem Name — "Group Photo"

There are $$$N$$$ people, each with a unique height. The height of the $$$i^{th}$$$ person is $$$i (1 \leq i \leq N)$$$. The $$$i^{th}$$$ person will smile in the photo if at least $$$A[i]$$$ people in the photo are shorter than him and at most $$$B[i]$$$ people in the photo are taller than him.

Find the largest group such that everyone will smile in the photo of this group. A group is a collection of randomly selected people from the given $$$N$$$ people.

Constraints:

  • $$$1 \leq N \leq 10^5$$$

  • $$$0 \leq A[i], B[i] \leq N$$$

Example Test Case
My O(N^2) approach

I cannot come up with a better solution for this. Any help would be greatly appreciated, thanks!

Tags external contest, question

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English t0rto1se 2022-07-29 20:20:20 1089 Initial revision (published)