The Celebrity Problem using Two-pointer approach
The idea is to use two pointers, one from start and one from the end. Assume the start person is A, and the end person is B. If A knows B, then A must not be the celebrity. Else, B must not be the celebrity. At the end of the loop, only one index will be left as a celebrity. Go through each person again and check whether this is the celebrity.
The Two Pointer approach can be used where two pointers can be assigned, one at the start and the other at the end, and the elements can be compared and the search space can be reduced.
Follow the steps below to solve the problem:
- Create two indices i and j, where i = 0 and j = n-1
- Run a loop until i is less than j.
- Check if i knows j, then i can’t be a celebrity. so increment i, i.e. i++
- Else j cannot be a celebrity, so decrement j, i.e. j–
- Assign i as the celebrity candidate
- Now at last check whether the candidate is actually a celebrity by re-running a loop from 0 to n-1 and constantly checking if the candidate knows a person or if there is a candidate who does not know the candidate.
- Then we should return -1. else at the end of the loop, we can be sure that the candidate is actually a celebrity.
Below is the implementation of the above approach:
// C++ program to find celebrity
// in the given Matrix of people
#include <bits/stdc++.h>
using namespace std;
#define N 4
int celebrity(int M[N][N], int n)
{
// This function returns the celebrity
// index 0-based (if any)
int i = 0, j = n - 1;
while (i < j) {
if (M[j][i] == 1) // j knows i
j--;
else // j doesnt know i so i cant be celebrity
i++;
}
// i points to our celebrity candidate
int candidate = i;
// Now, all that is left is to check that whether
// the candidate is actually a celebrity i.e: he is
// known by everyone but he knows no one
for (i = 0; i < n; i++) {
if (i != candidate) {
if (M[i][candidate] == 0
|| M[candidate][i] == 1)
return -1;
}
}
// if we reach here this means that the candidate
// is really a celebrity
return candidate;
}
int main()
{
int M[N][N] = { { 0, 0, 1, 0 },
{ 0, 0, 1, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 1, 0 } };
int celebIdx = celebrity(M, 4);
if (celebIdx == -1)
cout << ("No Celebrity");
else {
cout << "Celebrity ID " << celebIdx;
}
return 0;
}
// This code contributed by gauravrajput1
// Java program to find celebrity
// in the given Matrix of people
// Code by Sparsh_cbs
import java.io.*;
class GFG {
public static void main(String[] args)
{
int[][] M = { { 0, 0, 1, 0 },
{ 0, 0, 1, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 1, 0 } };
int celebIdx = celebrity(M, 4);
if (celebIdx == -1)
System.out.println("No Celebrity");
else {
System.out.println("Celebrity ID " + celebIdx);
}
}
public static int celebrity(int M[][], int n)
{
// This function returns the celebrity
// index 0-based (if any)
int i = 0, j = n - 1;
while (i < j) {
if (M[j][i] == 1) // j knows i
j--;
else // j doesnt know i so i cant be celebrity
i++;
}
// i points to our celebrity candidate
int candidate = i;
// Now, all that is left is to check that whether
// the candidate is actually a celebrity i.e: he is
// known by everyone but he knows no one
for (i = 0; i < n; i++) {
if (i != candidate) {
if (M[i][candidate] == 0
|| M[candidate][i] == 1)
return -1;
}
}
// if we reach here this means that the candidate
// is really a celebrity
return candidate;
}
}
# Python3 code
class Solution:
# Function to find if there is a celebrity in the party or not.
# return index if celebrity else return -1
def celebrity(self, M, n):
# code here
i = 0
j = n-1
candidate = -1
while(i < j):
if M[j][i] == 1:
j -= 1
else:
i += 1
candidate = i
for k in range(n):
if candidate != k:
if M[candidate][k] == 1 or M[k][candidate] == 0:
return -1
return candidate
n = 4
m = [[0, 0, 1, 0],
[0, 0, 1, 0],
[0, 0, 0, 0],
[0, 0, 1, 0]]
ob = Solution()
a = ob.celebrity(m, n)
if a == -1:
print("No Celebrity")
else:
print("Celebrity ID", a)
// C# program to find celebrity
// in the given Matrix of people
// Code by Sparsh_cbs
using System;
class GFG {
public static void Main(String[] args)
{
int[, ] M = { { 0, 0, 1, 0 },
{ 0, 0, 1, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 1, 0 } };
int celebIdx = celebrity(M, 4);
if (celebIdx == -1)
Console.Write("No Celebrity");
else {
Console.Write("Celebrity ID " + celebIdx);
}
}
public static int celebrity(int[, ] M, int n)
{
// This function returns the celebrity
// index 0-based (if any)
int i = 0, j = n - 1;
while (i < j) {
if (M[j, i] == 1) // j knows i
j--;
else // i knows j
i++;
}
// i points to our celebrity candidate
int candidate = i;
// Now, all that is left is to check that whether
// the candidate is actually a celebrity i.e: he is
// known by everyone but he knows no one
for (i = 0; i < n; i++) {
if (i != candidate) {
if (M[i, candidate] == 0
|| M[candidate, i] == 1)
return -1;
}
}
// if we reach here this means that the candidate
// is really a celebrity
return candidate;
}
}
// This code is contributed by shivanisinghss2110
// JavaScript program to find celebrity
// in the given Matrix of people
// Code by Sparsh_cbs
var M = [ [ 0, 0, 1, 0 ],
[ 0, 0, 1, 0 ],
[ 0, 0, 0, 0 ],
[ 0, 0, 1, 0 ] ];
var celebIdx = celebrity(M, 4);
if (celebIdx == -1)
console.log("No Celebrity");
else {
console.log(
"Celebrity ID " + celebIdx);
}
function celebrity( M, n)
{
// This function returns the celebrity
// index 0-based (if any)
var i = 0, j = n - 1;
while (i < j) {
if (M[j][i] == 1) // j knows i
j--;
else // i knows j
i++;
}
// i points to our celebrity candidate
var candidate = i;
// Now, all that is left is to check that whether
// the candidate is actually a celebrity i.e: he is
// known by everyone but he knows no one
for (i = 0; i < n; i++) {
if (i != candidate) {
if (M[i][candidate] == 0
|| M[candidate][i] == 1)
return -1;
}
}
// if we reach here this means that the candidate
// is really a celebrity
return candidate;
}
// This code is contributed by shivanisinghss2110
Output
Celebrity ID 2
Time Complexity: O(N), Iterating two times the array of size N.
Auxiliary Space: O(1) No extra space is required.
The Celebrity Problem
In a party of N people, only one person is known to everyone. Such a person may be present at the party, if yes, (s)he doesn’t know anyone at the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in the minimum number of questions.
We can describe the problem input as an array of numbers/characters representing persons in the party. We also have a hypothetical function HaveAcquaintance(A, B) which returns true if A knows B, and false otherwise. How can we solve the problem?
Examples:
Input:
MATRIX = { {0, 0, 1, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}, {0, 0, 1, 0} }
Output: id = 2
Explanation: The person with ID 2 does not know anyone but everyone knows himInput:
MATRIX = { {0, 0, 1, 0}, {0, 0, 1, 0}, {0, 1, 0, 0}, {0, 0, 1, 0} }
Output: No celebrity
Explanation: There is no celebrity.