Here is my Solution. I am not able to think of a better approach and this one is giving me a TLE on some test cases.
You can check two pointer approach here