Longest Meeting cell in graph


  • 1
    A
    This post is deleted!

  • 0
    A

    My python solution

    def nearest_meeting_cell(edges, a, b):
        visited_a = set()
        visited_b = set()
    
        while a != -1 or b != -1:
            if a != -1:
                if a in visited_a:
                    a = -1
                else:
                    visited_a.add(a)
    
                    if a in visited_b:
                        return a
                    a = edges[a]
    
            if b != -1:
                if b in visited_b:
                    b = -1
                else:
                    visited_b.add(b)
    
                    if b in visited_a:
                        return b
                    b = edges[b]
    
        return -1
    

    This O(log n) is kind of fishy: if your graph is some kind of balanced tree this is indeed log n, but there are some cases that clearly can't be solved in O(log n), if you take edge = [1,2,3, -1], C1 = 0 and C2 = 3 this is obviously O(n) and I do not know how one could do better.

    Some test cases:

    assert nearest_meeting_cell([0], 0, 0) == 0
    assert nearest_meeting_cell([-1], 0, 0) == 0
    assert nearest_meeting_cell([1, 0, 3, 4, 2], 0, 3) == -1
    assert nearest_meeting_cell([1, 0, 1, 4, 2], 0, 3) == 1
    assert nearest_meeting_cell([2, 4, 3, -1, 3], 0, 1) == 3
    assert nearest_meeting_cell([1, 2, 3, -1], 0, 2) == 2
    

  • 0
    A

    @AntoineWDG
    Input:-
    23
    4 4 1 4 13 8 8 8 0 8 14 9 15 11 -1 10 15 22 22 22 22 22 21
    9 2

    Output :- ?


Log in to reply
 

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