Editorialist: Kaustubh Khavnekar
Map data structure
The individual connections between devices A and B in a Rube Goldberg machine are given. Your task is to find the overall path of the Rube Goldberg machine.
Express connections from A to B and to B from A as two different maps. Find device which is in forward map but not reverse map and construct path starting from that device.
Each connection consists of two parts, A and B. The problem can be solved in linear time using a map data structure. Note that the starting device will not appear as the second part in any connection, since no other device has a connection to that device. We can find this device by first making two maps, from A to B (forward map) and then from B to A (reverse map). Then we iterate through all forward mappings, and find a device which has a forward mapping but no reverse mapping. This is the starting device. Starting from this device, we can traverse all edges in order using the forward mappings.
Solution can be found here.