1
\$\begingroup\$

Here is the problem.

In a town, there are N people labelled 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 trust, an array of pairs trust[i] = [a, b] representing that the person labelled a trusts the person labelled b.

If the town judge exists and can be identified, return the label of the town judge. Otherwise, return -1.

  • Example 1:

    Input: N = 2, trust = [[1,2]] Output: 2

  • Example 2:

    Input: N = 3, trust = [[1,3],[2,3]] Output: 3

  • Example 3:

    Input: N = 3, trust = [[1,3],[2,3],[3,1]] Output: -1

  • Example 4:

    Input: N = 3, trust = [[1,2],[2,3]] Output: -1

  • Example 5:

    Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]] Output: 3

Note:

  • 1 <= N <= 1000
  • trust.length <= 10000
  • trust[i] are all different
  • trust[i][0] != trust[i][1]
  • 1 <= trust[i][0], trust[i][1] <= N

And here is my solution.

(Logic :- Check the degree of every node, +1 for incoming and -1 for outgoing. If any node is having degree as N-1 then that is the node.)

public int findJudge(int N, int[][] trust) {
        // Create graph of N and then check degree, should be N-1
        final int NOT_FOUND = -1;
        final int trustArrayLength = trust.length;


        // Degree array should have value starting from 1 to N+1
        final int[] degreeArray = new int[N + 1];

        for (int i = 0; i < trustArrayLength; i++) {
            int[] itemInTrustArray = trust[i];

            // Since its outbound connection, decrease the degree by 1.
            degreeArray[itemInTrustArray[0]]--;

            // Since its inbound connection, increase the degree by 1.
            degreeArray[itemInTrustArray[1]]++;
        }

        // Now iterate though the degreeArray to find the index having degree as N-1.
        for (int i = 1; i <= N; i++) {
            if (degreeArray[i] == N - 1) {
                return i;
            }
        }
        return NOT_FOUND;
    }

Pleae let me know, the area of improvement.

\$\endgroup\$
1
\$\begingroup\$

This is a wonderfully succinct solution. I will make one point:

final int[] degreeArray = new int[N + 1];

This creates a never-used int at degreeArray[0]. I understand that this was a choice so as to be able to use a simple access by value of the trustees:

degreeArray[itemInTrustArray[0]]--;

In the interest of creating the minimum number of objects necessary, and thus using the least memory possible, I would recommend initializing degreeArray to length N

final int[] degreeArray = new int[N];

And then left shifting your insert by value statements

degreeArray[itemInTrustArray[0]--]--;
degreeArray[itemInTrustArray[1]--]++;

and finally updating your final for loop to account for this change to the zero-based indexing inherent to arrays

// Now iterate though the degreeArray to find the index having degree as N-1.
for (int i = 0; i < N; i++) {

Since you are working with int primitives, the math operators here would add only a near-vanishing amount to overall runtime, if that is a concern.

\$\endgroup\$
  • \$\begingroup\$ Thank you, it was really helpful. \$\endgroup\$ – Mosbius8 Apr 6 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.