Here is the video link where I have discussed the algorithm for this question in the best possible time complexity :https://youtu.be/HcMyvvJe_OE 
:
Please go through it and do like and share if u find it helpful 
3 Likes