LeetCode 997. Find the Town Judge (Easy) : NileshBlog.Tech

LeetCode 997. Find the Town Judge :Hey there, coding enthusiasts! Welcome back to another exciting coding session. Today’s problem is a treat—literally! We’re going to solve the “Find the Town Judge” or “LeetCode 997. ‘

The Steps to solve the “Find the Town Judge” problem can be broken down into the following steps:

Create an empty hash map (or unordered_map) called “trustCount” to store the trust relationships between citizens and the judge.

Iterate through the trust array and for each relationship, decrement the trust count for the citizen and increment the trust count for the judge in the “trustCount map“.
Iterate through the trustCount map from 1 to N (the total number of people in the town).
Check if there is a person with a trust count of N-1. If such a person exists, return their ID as they are the Town Judge.

If no such person is found, return -1 as there is no Town Judge in the town.

This algorithm uses a hash map (or unordered_map) to store the trust relationship between citizens and judge. By iterating through the trust array, we can keep track of the trust count of each person. And then by iterating through the map, we can check if there is a person with trust count N-1, if such a person exists, they are the Find the Town Judge.

Cpp

int findJudge(int N, vector<vector<int>>& trust) {
    unordered_map<int, int> trustCount;
    for (const auto& t : trust) {
        trustCount[t[0]]--;
        trustCount[t[1]]++;
    }
    for (int i = 1; i <= N; i++) {
        if (trustCount[i] == N - 1) {
            return i;
        }
    }
    return -1;
}

In this solution, we use an unordered_map to store the trust relationship between citizens and judge. For each relationship, we decrement the trust count of the citizen and increment the trust count of the judge. Then we iterate through the map and check if there is a person with a trust count of N-1, if such a person exists, they are the Town Judge.

The time complexity of this solution is O(n) where n is the number of trust relationship. The space complexity of this solution is O(n) as well where n is the number of people in the town.

class Solution:
    def findJudge(self, N: int, trust: List[List[int]]) -> int:
        trustCount = [0] * (N + 1)
        for t in trust:
            trustCount[t[0]] -= 1
            trustCount[t[1]] += 1
        for i in range(1, N+1):
            if trustCount[i] == N - 1:
                return i
        return -1

class Solution {
    public int findJudge(int N, int[][] trust) {
        int[] trustCount = new int[N + 1];
        for (int[] t : trust) {
            trustCount[t[0]]--;
            trustCount[t[1]]++;
        }
        for (int i = 1; i <= N; i++) {
            if (trustCount[i] == N - 1) {
                return i;
            }
        }
        return -1;
    }
}

const findJudge = (N, trust) => {
    let trustCount = new Array(N + 1).fill(0)
    for (let i = 0; i < trust.length; i++) {
        trustCount[trust[i][0]]--;
        trustCount[trust[i][1]]++;
    }
    for (let i = 1; i <= N; i++) {
        if (trustCount[i] === N - 1) {
            return i;
        }
    }
    return -1;
}

int findJudge(int N, List<List<int>> trust) {
    var trustCount = List.filled(N + 1, 0);
    for (var i = 0; i < trust.length; i++) {
        trustCount[trust[i][0]]--;
        trustCount[trust[i][1]]++;
    }
    for (var i = 1; i <= N; i++) {
        if (trustCount[i] == N - 1) {
            return i;
        }
    }
    return -1;
}

List of Some important Leet code Questions:

Leet Code 2612 Minimum Reverse Operations

Cpp

Leave a Comment