[Share Solution] Java, Greedy, Stack, 15ms with explanation


  • 30
    F

    Noticed some folks are using Hierholzer's algorithm to find a Eulerian path.

    My solution is similar, considering this passenger has to be physically in one place before move to another airport, we are considering using up all tickets and choose lexicographically smaller solution if in tie as two constraints.

    Thinking as that passenger, the passenger choose his/her flight greedy as the lexicographical order, once he/she figures out go to an airport without departure with more tickets at hand. the passenger will push current ticket in a stack and look at whether it is possible for him/her to travel to other places from the airport on his/her way.

    Please let me know if you have any suggestions.

        public List<String> findItinerary(String[][] tickets) {
            List<String> ans = new ArrayList<String>();
            if(tickets == null || tickets.length == 0) return ans;
            Map<String, PriorityQueue<String>> ticketsMap = new HashMap<>();
            for(int i = 0; i < tickets.length; i++) {
                if(!ticketsMap.containsKey(tickets[i][0])) ticketsMap.put(tickets[i][0], new PriorityQueue<String>());
                ticketsMap.get(tickets[i][0]).add(tickets[i][1]);
            }
    
            String curr = "JFK";
            Stack<String> drawBack = new Stack<String>();
            for(int i = 0; i < tickets.length; i++) {
                while(!ticketsMap.containsKey(curr) || ticketsMap.get(curr).isEmpty()) {
                    drawBack.push(curr);
                    curr = ans.remove(ans.size()-1);
                }
                ans.add(curr);
                curr = ticketsMap.get(curr).poll();
            }
            ans.add(curr);
            while(!drawBack.isEmpty()) ans.add(drawBack.pop());
            return ans;
        }

  • 1
    A

    Hello,
    I have some questions about the for loop and the stack.
    What is the 'ans' means when the for loop is over?
    Why the order of items in the stack equals to the order of the routine?
    Thank you!


  • 1
    F

    Good questions! Hope my answer helps

    What is the 'ans' means when the for loop is over?
    It means the first part of flights order from JFK which is strictly follow lexicographical order.

    Why the order of items in the stack equals to the order of the routine?
    The remove from tail of ans operation reverse the second part of flight order once, and the pop out from stack into ans reverse the flight order back. Thus the order of the routine is preserved.

    I haven't consider edge cases where you cannot find a routine for all air tickets.


  • 0
    A

    I figure out that there is a patter in the route. There can be several loops in the route, but only one leg in the route. So the stack stores the order of the leg, and the leg is the last part of the whole route. Am I right?


  • 0
    F

    No, the stack is not exactly about the tail you described.

    For this use case:

    JFK->A, JFK->B
    A->C,
    A->D, D->A,
    B->JFK

    In this case A-> C is the tail, A->D, D->A is a loop.
    However all tickets will be pushed into stack except JFK->B and B->JFK


  • 0
    H

    Hello, I calculated this use case by hand:

    JFK->A, JFK->B A->C, A->D, D->A, B->JFK

    And I have a question, all the tickets pushed into stack are part of the tail side in graph, does that mean all the tickets from the route which has a tail will be pushed into stack?

    Thank you!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.