DSA 450 Notes

Problem Statement

In a party of n people, a celebrity is defined as someone who:

Is known by everyone
Knows no one

Given a matrix M where M[i][j] = 1 means person i knows person j, find the celebrity. If no celebrity exists, return -1.

Example:

Input: M = [[0, 0, 1, 0],
            [0, 0, 1, 0],
            [0, 0, 0, 0],
            [0, 0, 1, 0]]
Output: 2

Explanation: Person 2 is known by everyone (column 2 is all 1s except M[2][2])
            and knows no one (row 2 is all 0s)

Approach 1: Brute Force

Intuition

For each person, check if they could be a celebrity by verifying both conditions: they know no one (row check) and everyone knows them (column check).

Algorithm

For each person i from 0 to n-1
Check if person i knows anyone (row i should be all 0s)
Check if everyone knows person i (column i should be all 1s, except M[i][i])
If both conditions satisfied, i is the celebrity

java

public class CelebrityProblem {
    static int[][] M;
    
    static boolean knows(int a, int b) {
        return M[a][b] == 1;
    }
    
    public static int findCelebrityBruteForce(int n) {
        for (int i = 0; i < n; i++) {
            boolean isCelebrity = true;
            
            // Check if i knows anyone
            for (int j = 0; j < n; j++) {
                if (i != j && knows(i, j)) {
                    isCelebrity = false;
                    break;
                }
            }
            
            if (!isCelebrity) continue;
            
            // Check if everyone knows i
            for (int j = 0; j < n; j++) {
                if (i != j && !knows(j, i)) {
                    isCelebrity = false;
                    break;
                }
            }
            
            if (isCelebrity) return i;
        }
        
        return -1;
    }
    
    public static void main(String[] args) {
        M = new int[][] {
            {0, 0, 1, 0},
            {0, 0, 1, 0},
            {0, 0, 0, 0},
            {0, 0, 1, 0}
        };
        
        System.out.println("Celebrity: " + findCelebrityBruteForce(4));  // 2
    }
}

Complexity Analysis

Time Complexity: O(n^2) - for each of n people, check n-1 others
Space Complexity: O(1)

Approach 2: Using Stack (Optimal)

Intuition

Use elimination: if A knows B, A can't be celebrity; if A doesn't know B, B can't be celebrity. Push all people to stack, then compare pairs and eliminate one. The remaining candidate is verified.

Algorithm

Push all people (0 to n-1) onto stack
While stack has more than one person:
- Pop two people a and b
- If a knows b: a is not celebrity, push b back
- Else: b is not celebrity, push a back
Verify the last remaining person is actually a celebrity

java

import java.util.*;

public class CelebrityProblem {
    private int[][] M;
    private int n;
    
    public CelebrityProblem(int[][] matrix, int size) {
        this.M = matrix;
        this.n = size;
    }
    
    private boolean knows(int a, int b) {
        return M[a][b] == 1;
    }
    
    public int findCelebrity() {
        Stack<Integer> stack = new Stack<>();
        
        // Push all people onto stack
        for (int i = 0; i < n; i++) {
            stack.push(i);
        }
        
        // Eliminate n-1 people
        while (stack.size() > 1) {
            int a = stack.pop();
            int b = stack.pop();
            
            if (knows(a, b)) {
                // a knows b, so a can't be celebrity
                stack.push(b);
            } else {
                // a doesn't know b, so b can't be celebrity
                stack.push(a);
            }
        }
        
        // Verify the candidate
        int candidate = stack.peek();
        
        // Check if candidate knows anyone
        for (int i = 0; i < n; i++) {
            if (i != candidate && knows(candidate, i)) {
                return -1;
            }
        }
        
        // Check if everyone knows candidate
        for (int i = 0; i < n; i++) {
            if (i != candidate && !knows(i, candidate)) {
                return -1;
            }
        }
        
        return candidate;
    }
    
    public static void main(String[] args) {
        int[][] M = {
            {0, 0, 1, 0},
            {0, 0, 1, 0},
            {0, 0, 0, 0},
            {0, 0, 1, 0}
        };
        
        CelebrityProblem cp = new CelebrityProblem(M, 4);
        System.out.println("Celebrity: " + cp.findCelebrity());  // 2
    }
}

Complexity Analysis

Time Complexity: O(n) - elimination takes n-1 comparisons, verification takes 2n
Space Complexity: O(n) - stack to store all people

Approach 3: Two Pointer (Most Optimal Space)

Intuition

Use two pointers at start and end. Compare them to eliminate one. Move the pointer of the eliminated person towards the other.

Key Takeaways

Elimination principle: Each comparison eliminates one candidate
Stack helps manage the elimination process systematically
After elimination, verification is essential - the candidate might still not be a celebrity
Two-pointer approach achieves O(1) space
The problem uses the property that exactly one comparison is needed to eliminate one candidate
This pattern is useful in tournament-style elimination problems

The celebrity Problem

Problem Statement

Approach 1: Brute Force

Intuition

Algorithm

Complexity Analysis

Approach 2: Using Stack (Optimal)

Intuition

Algorithm

Complexity Analysis

Approach 3: Two Pointer (Most Optimal Space)

Intuition

Key Takeaways