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:

- Find the Index from which 0 starts Beginner
- Print All Combinations of subset of size K from Given Array Hard
- Longest Shared Prefix Sequence in a String Medium
- Find Kth Smallest or Largest element in an Array Medium
- Given an array, find the number of all pairs with odd sum. Medium