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:

- Print sorted unique elements of a given array Beginner
- Find Subarray with Sum Equal to a Target Value Medium
- Find the first repeating character in a given string Beginner
- Stack Java Class - Explained Beginner
- Replace array elements with maximum element on the right. Medium