Swift solution with full comments


  • 0
    S

    There is no Swift option for this problem, but here's a solution for the curious. This wasn't my solution, but an adaptation of several clever Java solutions to a Swift one with full comments on the logic.

    class Solution {
        func findCelebrity(n: Int) -> Int {
            var celeb = 0
            
            // there can only be 1 person at the
            // party who knows nobody, that is the key
            // in this pass
            // 
            // in addition, if celeb knows i, they can't
            // be the celeb, since prior i's are all unknown
            // they can't be the celeb making i the next 
            // potential candidate
            for i in 1..<n {
                if knows(celeb, i) {
                    celeb = i
                }
            }
            
            // at this point, celeb should know
            // nobody of higher n than themsevles
            
            // confirm that celeb is:
            // 1) knows nobody <= celeb
            // 2) known by all
            for j in 0..<n where celeb != j {
                if (j < celeb && knows(celeb, j)) || !knows(j, celeb) {
                    // there is no celeb
                    return -1
                }
            }
            
            // we found the celeb
            return celeb
        }
    }
    

Log in to reply
 

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