How can we be sure that the greedy approach to connect a white dot to nearest black dot is the most optimal one? Can there be cases where this will fail?
Doubt in Connecting Wires
hi @atharv think logically, suppose we are not connecting it to the nearest possible dot, but to any other dot. Then the length of the wire will only increase right? There is no way it could decrease, if we dont choose the nearest dot. So by choosing the nearest available dot each time, we are ensuring that no extra wire is being used. If we chose any other point, it’d result in more wire being used, and thus the final answer will not be optimal.
It is often very difficult to provide a concrete mathematical proof for greedy algorithms so you have to think logically only. But yes, this approach will work for all the cases.
Please mark your doubt as resolved in case of no further queries 
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.