Java concise recursive divide and conquer & BONUS 3-line Java 8 stream solution :)


  • 1
    A
    public int findCelebrity(int n) {
        int c = divide(0, n-1); 
        if (c == -1) return -1;
        for (int i = 0; i < n; i++)
            if (i != c && knows(c,i)) return -1;
        return c;
    }
    
    public int divide(int l, int h) {
        if (h <= l) return l;
        int m = (l + h) / 2;
        return select(divide(l, m), divide(m+1, h));
    }
    
    private int select(int c1, int c2) {
        if (c1 == c2) return c1;
        else if (c1 == -1) return c2;
        else if (c2 == -1) return c1;
        else if (knows(c1,c2)) return c2;
        else if (knows(c2,c1)) return c1;
        else return -1;
    }
    

    BONUS 3-liner!!! :) Inspired by czonzhu's solution.

    @czonzhu has a good explanation of his 2 iterations approach. For those who are interested in how I transformed it into Java's streaming solution:

    • In the first iteration we look at 1 to n-1 (inclusive) people in the party. We initialize our iteration assuming that person 0 is the celebrity. Then we check if person i knows c. If true, then c is still likely to be a celebrity, otherwise we swap c and i and suppose i is the celebrity.
    1. In Java 8 IntStream is simply a sequence of integers.

    2. Adding the modifier 'range' to it specifies the range of the integers.

    3. Adding the modifier 'forEach' includes the logic that has to be performed for every element i in the defined range.

    • Now that we have our candidate c from the first iteration we want to confirm that he/she is indeed the celebrity. We iterate over all people in range 0 to n-1 (inclusive). For each person we check if this person is not a c (to avoid knows(c,c) which will always return true) and whether he/she doesn't know our candidate celebrity c or c knows i. If any of this conditions is true then our candidate c is not a celebrity.
    1. Similarly to the previous step we create an IntStream of given range.

    2. Adding the modifier 'filter' removes all elements that do not satisfy the filtering condition (described above).

    3. If At least one person satisfies our filtering condition, i.e. disconfirms that c is a celebrity, we leave this person in the stream. Therefore, when we perform a count() on the stream we get the number of people who invalidated that c is a celebrity. If this count is > 0 we return -1, otherwise c is confirmed to be a celebrity.

    A quick note, c in this case is a global field because streams in Java 8 can only use final or effectively final variables. Local variables of the method will not work because when the method is popped off the stack the local variables are dereferenced.

    private int c = 0;
    public int findCelebrity(int n) {
        IntStream.range(1,n).forEach(i -> c = knows(i,c) ? c : i);
        return IntStream.range(0,n).filter(i -> c != i && (knows(c,i) || !knows(i,c))).count() > 0 ? -1 : c;
    }
    

  • 0
    E

    It would be much more helpful if you write down your explanation for the second coding :)


  • 0
    A

    Added a very thorough description for those who are interested :)


  • 0
    E

    Thanks a lot.


  • 0

    Better use findFirst().isPresent() instead of count() > 0 to avoid evaluating the whole stream. And you can use the old array trick to make c a local mutable but it will probably be slower than a field.


  • 0
    T

    In select function, I noticed that if c1 != c2 and c1 c2 dont' know each other, it will return -1. But, it cannot shows that whether c1 or c2 knows c which may be selected in process.
    For example. [a b c d e f]; 1, b,c knows a 2,d,e don't know each other and they don't know a 3 a,b,c knows f; the answer should be -1 means no celebrity.
    Correct me if I understand it in wrong,thx!


Log in to reply
 

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