This post is completed by 3 users

  • 2
Add to List

537. Departure and Destination Cities in a given itinerary

You are on a business trip and traveling from one city to another. you have a stack of unsorted flight boarding passes. The only departure city and destination city are on the boarding pass. how do you find the first departure city and your final destination city,


[Dallas, Austin], [Houston, Dallas], [Austin, Seattle]
Output: Departure: Houston, Destination: Seattle

[Dallas, New York], [Dallas, Austin], [Austin, Dallas], [New York, Seattle], [Seattle, Houston]
Output: Departure: Dallas, Destination: Houston


Construct a map with a city name as a key and an integer as a value. For any boarding, subtract the 1 from the value against the departure city and add the 1 to the value against the destination city in the map. Once you process all the boarding passes, on the map you will have only one city with count as -1 and only one city with count as +1. These are the first departure and final destination cities respectively. 


Departure: Dallas, Destination: Houston

Reference: careercup