Party in Town

Problem Overview

Pick one house so the farthest other house is as close as possible.

Intuition

Pick one house so the farthest other house is as close as possible. On a tree that value is the radius, which equals ceil(diameter / 2). Find the diameter with two BFS passes from a farthest-node endpoint.

Algorithm

1BFS from house 0 to find a farthest node A.
2BFS from A to find the farthest distance; that length is the diameter.
3Return (diameter + 1) / 2.

Example Walkthrough

Input: tree path of 4 edges (diameter 4)

1. First BFS reaches one end of the path.
2. Second BFS measures diameter 4.
3. Best party house sits near the middle with max distance 2.

Output: 2

Common Pitfalls

• Adjacency entries may be 1-based house numbers; convert before indexing.
• Do not BFS from every house; two passes already give the diameter.
• Use integer (d + 1) / 2 for ceil(d / 2).
• The graph is a tree, so distances are unique paths.

Party in Town.java

Java

// Approach: The best party house minimizes the farthest house distance, i.e.
// the tree radius. Two BFS runs find a diameter; radius is (diameter + 1) / 2.
// Complexity: O(n) time and O(n) extra space.
import java.util.*;

class Solution {

    public int partyHouse(ArrayList<ArrayList<Integer>> adj) {
        int[] first = bfs(adj, 0);
        int[] second = bfs(adj, first[0]);
        return (second[1] + 1) / 2;
    }

    // Returns {farthestNode, maxDist} from start.
    private int[] bfs(ArrayList<ArrayList<Integer>> adj, int start) {
        int n = adj.size();
        boolean[] visited = new boolean[n];
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{start, 0});
        visited[start] = true;

        int farthest = start;
        int maxDist = 0;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int node = cur[0];
            int dist = cur[1];
            if (dist > maxDist) {
                maxDist = dist;
                farthest = node;
            }

            for (int next : adj.get(node)) {
                next--; // 1-based house numbers in the adjacency list
                if (!visited[next]) {
                    visited[next] = true;
                    q.offer(new int[]{next, dist + 1});
                }
            }
        }

        return new int[]{farthest, maxDist};
    }
}

Was this solution helpful?