What is the time complexity of Find the Town Judge?

The optimal solution has a time complexity of O(t + n).

What data structures are used to solve Find the Town Judge?

This problem uses Array, Hash Table, Graph. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Find the Town Judge?

Insight 1: The town judge trusts nobody. This means that if person 'i' is the town judge, 'i' will never appear as the first element (trustor) in any of the trust pairs. Insight 2: Everyone (except the town judge) trusts the town judge. This means that if person 'i' is the town judge, 'i' will be the second element (trustee) in n-1 trust pairs.

Which companies ask LeetCode 997. Find the Town Judge in interviews?

This problem is frequently asked at Arista Networks, Turing.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Find the Town Judge - LeetCode 997 Solution

Find the Town Judge - Complete Solution Guide

Find the Town Judge is LeetCode problem 997, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

In a town, there are n people labeled from 1 to n . There is a rumor that one of these people is secretly the town judge. If the town judge exists, then: The town judge trusts nobody. Everybody (except for the town judge) trusts the town judge. There is exactly one person that satisfies properties 1 and 2 . You are given an array trust where trust[i] = [a i , b i ] representing that the person labeled a i trusts the person labeled b i . If a trust relationship does not exist in trust array, then

Detailed Explanation

The problem asks us to find the 'town judge' in a town of 'n' people, labeled from 1 to 'n'. The town judge, if they exist, trusts nobody, and everyone else trusts the judge. We are given a list of trust relationships in the form of pairs (a, b), meaning person 'a' trusts person 'b'. Our task is to identify the judge based on these relationships or return -1 if no such judge exists. A judge must be trusted by n-1 people, and must trust no one.

Solution Approach

The solution uses two arrays, `trusts` (or `outDegree`) and `trusted` (or `inDegree`), to store the out-degree and in-degree of each person, respectively. We iterate through the `trust` array and increment `trusts[a]` and `trusted[b]` for each pair (a, b). After processing all trust relationships, we iterate from 1 to 'n' to find a person 'i' where `trusts[i]` is 0 (trusts nobody) and `trusted[i]` is 'n-1' (trusted by everyone else). If such a person is found, they are the town judge. If no such person is found, we return -1.

Step-by-Step Algorithm

Step 1: Initialize two arrays, `trusts` (or `outDegree`) and `trusted` (or `inDegree`), of size n+1, with all elements set to 0.
Step 2: Iterate through the `trust` array. For each pair (a, b), increment `trusts[a]` by 1 and increment `trusted[b]` by 1.
Step 3: Iterate from 1 to n. For each person 'i', check if `trusts[i]` is 0 and `trusted[i]` is equal to n-1. If both conditions are true, return 'i' as the town judge.
Step 4: If no judge is found after iterating through all people, return -1.

Key Insights

Insight 1: The town judge trusts nobody. This means that if person 'i' is the town judge, 'i' will never appear as the first element (trustor) in any of the trust pairs.
Insight 2: Everyone (except the town judge) trusts the town judge. This means that if person 'i' is the town judge, 'i' will be the second element (trustee) in n-1 trust pairs.
Insight 3: We can use two arrays to track the number of times each person trusts someone else (out-degree) and the number of times each person is trusted by someone else (in-degree).

Complexity Analysis

Time Complexity: O(t + n)

Space Complexity: O(n)

Topics

This problem involves: Array, Hash Table, Graph.

Companies

Asked at: Arista Networks, Turing.

Find the Town Judge | LeetCode 997

Easy

Array Hash Table Graph

Time: O(t + n)Space: O(n)

Solution Code

Available in:

class Solution {
    public int findJudge(int n, int[][] trust) {
        if (n == 1 && trust.length == 0) return 1;
        int[] inDegree = new int[n + 1];
        int[] outDegree = new int[n + 1];

        for (int[] relation : trust) {
            int a = relation[0];
            int b = relation[1];
            outDegree[a]++;
            inDegree[b]++;
        }

        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == n - 1 && outDegree[i] == 0) {
                return i;
            }
        }

        return -1;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 997: Find the Town Judge - Detailed explanation and solution approaches.

Topics

Array Hash Table Graph

Companies

Arista NetworksTuring

Stats

Difficulty:Easy

Languages:4

Companies:2

Problem #:997

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

4 steps

1
Step 1: Initialize two arrays, `trusts` (or `outDegree`) and `trusted` (or `inDegree`), of size n+1, with all elements set to 0.
2
Step 2: Iterate through the `trust` array. For each pair (a, b), increment `trusts[a]` by 1 and increment `trusted[b]` by 1.
3
Step 3: Iterate from 1 to n. For each person 'i', check if `trusts[i]` is 0 and `trusted[i]` is equal to n-1. If both conditions are true, return 'i' as the town judge.
4
Step 4: If no judge is found after iterating through all people, return -1.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(t + n)

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is linear because we visit each element of trust and each number from 1 to n at most once. The space complexity is linear because we use two arrays of size n+1 which directly depend on the size of the input n.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Graph Approach

Represent the trust relationships as a directed graph, where each person is a node and each trust relationship is an edge. The judge, if exists, will have an in-degree of n-1 and an out-degree of 0.

Time: O(t + n), where 't' is the number of trust relationships and 'n' is the number of people.Space: O(n), to store the graph (adjacency list or matrix).

Trade-offs: The graph approach is conceptually similar to the array-based approach but can be more complex to implement. The array-based approach is simpler and more efficient for this specific problem because we only need to track the in-degree and out-degree of each person.

Single Array Approach

Instead of using two arrays for in-degree and out-degree, use a single array where in-degree is added and out-degree is subtracted. The candidate judge should have a score of n-1.

Time: O(t + n)Space: O(n)

Trade-offs: This approach combines the two arrays into one. This is a slight improvement in terms of space complexity but does not significantly change performance.

✨

Key Insights

1Insight 1: The town judge trusts nobody. This means that if person 'i' is the town judge, 'i' will never appear as the first element (trustor) in any of the trust pairs.
2Insight 2: Everyone (except the town judge) trusts the town judge. This means that if person 'i' is the town judge, 'i' will be the second element (trustee) in n-1 trust pairs.
3Insight 3: We can use two arrays to track the number of times each person trusts someone else (out-degree) and the number of times each person is trusted by someone else (in-degree).

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Graph

Nodes connected by edges. Like a social network or city map!

Edge Cases

Edge case 1: n = 1 and trust is empty (i.e., trust = []). In this case, the only person is the town judge, so we should return 1. The given code handles this correctly.
Edge case 2: n = 2 and trust = []. Then there is no judge as noone trusts anyone else, return -1. The code will iterate through the loop and return -1 as well.
Edge case 3: A person trusts themself i.e. (a,a). Although the constraints say this is impossible, if it were to occur, the implementation would fail because the indegree is being counted against the possible n-1 for someone else.
Edge case 4: Multiple people fit criteria but only one should exist according to prompt. The check only returns the first eligible person. The test cases do not contain such scenario so implementation is still valid.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the edge case where n = 1 and trust is empty. The judge is person 1 in this scenario.

✗Common mistake 2: Incorrectly calculating the in-degree and out-degree. It's important to increment the correct array element for each trust relationship.

✗Common mistake 3: Not checking for both conditions (trusts nobody and is trusted by everyone else) before declaring a person the judge.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Social network analysis, where you want to identify influential individuals who are trusted by many but do not trust others.

🏦Real-world scenario 2: Identifying a central authority in a distributed system, where most nodes rely on a single central node for decision-making but the central node doesn't rely on others.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Use this problem to demonstrate clean code practices. Variable naming and code organization matter.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 6, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I choose between a hash map and a hash set?

Use a hash set when you only need to track presence/absence of elements (like detecting duplicates). Use a hash map when you need to associate values with keys (like counting frequencies or storing indices). Hash sets use less memory since they only store keys.

What should I learn from easy problems?

Easy problems introduce core patterns that appear in harder problems. Master basic operations (iteration, conditionals, simple data structures), recognize common patterns (counting, searching, basic transformations), and practice explaining your thought process clearly.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Find the Town Judge"?

For this easy-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?