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,

Example: 

[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

Solution: 

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. 

Output:

Departure: Dallas, Destination: Houston

Reference: careercup

Related Problems:

- Identifying Maximum Gain from Sequential Elements Medium
- Kadane's Algorithm - Maximum Subarray Problem Medium
- Print all sub sequences of a given array Hard
- Count number of pairs in an array with sum = K Medium
- Given an array, rank its elements Beginner