Cheapest Flights Within K Stops


  • 0

    Click here to see the full article post


  • 4

    @awice. Thanks for your article. I am confused about the use of HashMap in Approach #2: Dijkstra's.
    I tested the code snippet below:

    Map<int[], Integer>  map = new HashMap<>();
    map.put(new int[] {1,2}, 1);
    System.out.print(map.get(new int[] {1,2}));
    

    The result is null. In this case, if the key is an int[] array, HashMap doesn't work.
    Could you please explain a bit about how your HashMap<int[ ], Integer> work in this solution?
    Thank you.


  • 0
    B

    I'm confused about the complexity analysis of approach 2. How does the algorithm prevent trying all possible (place, #stop) pairings?


  • 1
    B

    I suspect approach 2 would not have nlogn complexity for the following case:
    Take a chain graph of length n, where node i has a directed edge to node i+1, w/ a cost of c.
    node 0 has directed edge to node u where 0<u<=n/2 of cost 2c*u.
    src is 0 and sink is n-1.
    k is n/2.


  • 1
    C

    Solution1 produce wrong answer for this test case:
    4
    [[0,1,100],[0,2,300],[0,3,500],[1,2,100],[2,3,100]]
    0
    3
    1

    Expected answer should be 400, but the output is 300.


  • 1
    R

    For Approch 1, the pre and dis array would be updated together because of the sentence "pre = dis", I don't think it is correct, even it could pass the test cases. Since two different rounds would interfere with each other.


  • 0
    C

    @brendon4565 nlogn is obviously wrong


  • 0
    M

    @robinlzl1989 said in Cheapest Flights Within K Stops:

    For Approch 1, the pre and dis array would be updated together because of the sentence "pre = dis", I don't think it is correct, even it could pass the test cases. Since two different rounds would interfere with each other.

    Right, this caused the @ccwei 's test case to fail. The line should be replaced with
    System.arraycopy(dis, 0 , pre, 0, n);


  • 0
    A

    @awice int[][] graph = new int[n][n];
    this line makes complexity O(n*n)


  • 1
    K

    I like to point out that Approach 1 is essentially a modified Bellman-Ford Algorithm with two differences. First, the original Bellman-Ford does the same kind of relaxation for all edges for n - 1 rounds, and this modified version K + 1 rounds. Second, the original Bellman-Ford use one array to keep track of the estimate of the distance of all nodes from source, and so at the round i of relaxation, the number of stops of the path reaching the some nodes may be far greater than i. This version use two arrays pre and dis to make sure that after i round of relaxation, the number of stops in the cheapest path reaching every nodes is less than i.


  • 0

    @awice I'm surprised you used int[] as the key and got accepted. Can you explain why does it work? To my knowledge an int array should not work as the key for a map since it doesn't override equals() and hashcode(). Thanks.


  • 0

    After review, Approach 1 was incorrect in how it handled copying over the previous array: using the shallow copy "pre = dis" had unintended side effects that were not caught by previous test cases. The actual idea of the algorithm was still valid. The approach has been modified slightly to now use dist[i&1] and dist[~i&1] as the two rows "dis" and "pre", which is accepted. Thanks everyone for the feedback.


  • 0

    @xxj79 Actually, I was mistaken - it doesn't work. I replaced the algorithm with a simple encoding of the tuple into an integer.


  • 0
    M

    @brendon4565 said in Cheapest Flights Within K Stops:

    I'm confused about the complexity analysis of approach 2. How does the algorithm prevent trying all possible (place, #stop) pairings?

    Same question. I believe the runtime should be K(E + n * log(Kn)), ignoring the graph matrix initialization


  • 0
    M

    Also, for solution 2, the hashmap can be replaced by a set, since the priority queue would always pop the costs in increasing order, so the new costs would never be smaller than previously seen costs of the same k value. The modified code is AC'ed

    class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        int[][] graph = new int[n][n];
        for (int[] flight: flights)
            graph[flight[0]][flight[1]] = flight[2];
    
        Set<Integer> best = new HashSet();
    
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, 0, src});
    
        while (!pq.isEmpty()) {
            int[] info = pq.poll();
            int cost = info[0], k = info[1], place = info[2];
            int key = k * 1000 + place;
            if (k > K+1 || best.contains(key))
                continue;
            best.add(key);
            if (place == dst)
                return cost;
    
            for (int nei = 0; nei < n; ++nei) if (graph[place][nei] > 0) {
                if (!best.contains((k+1) * 1000 + nei)) {
                    int newcost = cost + graph[place][nei];
                    pq.offer(new int[]{newcost, k+1, nei});
                }
            }
        }
    
        return -1;
    }
    

    }


  • 0
    H

    solution 2, time complexity should be Elogkn?


  • 0
    M

    what's the 1000 here, why do you use 1000?


Log in to reply
 

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