Geek town has N Houses numbered from 1 to N. They are connected with each other via N-1 bidirectional roads. Given an adjacency list adj to represent the connections. To host the optimal party, you need to identify the house from which the distance to the farthest house is minimum. Find this distance.
Example 1:
Input: 
N = 4
adj = {{2},{1,3,4},{2},{2}} 
Output: 1
Explaination: 
Party should take place at house number 2. 
Maximum distance from house number 2 is 1.
Example 2:
Input:
N = 4
adj = {{2},{1,3},{2,4},{3}}
Output:
2
Explanation:
Party should take place at house number 2 or 3.
So, the minimum distance between the farthest
house and the party house is 2.
Your Task:
You do not need to read input or print anything. Your task is to complete the function partyHouse() which takes N and adj as input parameters and returns the minimum possible distance to the farthest house from the house where the party is happening.
Expected Time Complexity: O(N*N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 1000
1 <= adj[i][j] <= N

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3



class Solution:

    def partyHouse(self, N, adj):

        # code here

Solutions:
from collections import deque

class Solution:

	def partyHouse(self, N, adj):
		ans = N
		for i in range(1, N + 1):
			dist = [-1] * (N + 1)
			dist[i] = 0
			q = deque()
			q.append(i)
			max_dist = 0
			while len(q) > 0:
				v = q.popleft()
				for w in adj[v]:
					if dist[w] == -1:
						dist[w] = dist[v] + 1
						max_dist = max(max_dist, dist[w])
						q.append(w)
			ans = min(ans, max_dist)
		return ans


class Solution:

	def solve(self, curr, visited, adj):
		dist = 0
		depth = 1
		visited[curr] = True
		for i in adj[curr]:
			if not visited[i]:
				(dist2, depth2) = self.solve(i, visited, adj)
				dist = max(dist, dist2, depth + depth2 - 1)
				depth = max(depth, depth2 + 1)
		return (dist, depth)

	def partyHouse(self, N, adj):
		(dist, _) = self.solve(1, [False] * (N + 1), adj)
		return dist + 1 >> 1


import collections

class Solution:

	def partyHouse(self, N, adj):
		indegree = {}
		q = collections.deque([])
		visited = set()
		for i in range(1, N + 1):
			indegree[i] = len(adj[i])
			if indegree[i] == 1:
				q.append(i)
				visited.add(i)
		level = 0
		while len(visited) < N:
			for k in range(len(q)):
				node = q.popleft()
				for nextV in adj[node]:
					if nextV in visited:
						continue
					indegree[nextV] -= 1
					if indegree[nextV] == 1:
						q.append(nextV)
						visited.add(nextV)
			level += 1
		if len(q) == 2:
			return level + 1
		else:
			return level


class Solution:

	def partyHouse(self, N, adj):

		def dfs(n, d, vis, res):
			vis.add(n)
			res[0] = max(res[0], d)
			for ech in adj[n]:
				if ech not in vis:
					dfs(ech, d + 1, vis, res)
		ans = 10 ** 10
		for i in range(1, N + 1):
			res = [0]
			vis = set()
			dfs(i, 0, vis, res)
			ans = min(ans, res[0])
		return ans


import sys

def dfs(d, node, adj, dist):
	d[node] = dist
	for child in adj[node]:
		if dist + 1 < d[child]:
			dfs(d, child, adj, dist + 1)

def minDist(N, adj):
	ans = sys.maxsize
	for i in range(1, N + 1):
		d = [sys.maxsize for i in range(N + 1)]
		dfs(d, i, adj, 0)
		dist = 0
		for j in range(1, N + 1):
			dist = max(dist, d[j])
		ans = min(ans, dist)
	return ans

class Solution:

	def partyHouse(self, N, adj):
		return minDist(N, adj)


class Solution:

	def partyHouse(self, N, adj):
		M = [2 ** 31]

		def dfs(node, adj, vis, n, m):
			n[0] = n[0] + 1
			vis[node] = True
			for el in adj[node]:
				if vis[el] == False:
					dfs(el, adj, vis, n, m)
			m[0] = max(m[0], n[0] - 1)
			n[0] = n[0] - 1
		for node in range(1, N + 1):
			n = [0]
			m = [0]
			vis = [False for i in range(N + 1)]
			dfs(node, adj, vis, n, m)
			M[0] = min(M[0], m[0])
		return M[0]


class Solution:

	def helper(self, node, distance):
		if self.visited[node]:
			return
		self.visited[node] = 1
		for i in adj[node]:
			self.res[i - 1] = min(self.res[i - 1], distance + 1)
			self.helper(i - 1, distance + 1)
		self.visited[node] = 0

	def partyHouse(self, N, adj):
		adj.pop(0)
		self.temp = [float('inf') for i in range(N)]
		self.visited = [0 for i in range(N)]
		for i in range(N):
			self.res = [float('inf') if i != j else 0 for j in range(N)]
			self.helper(i, 0)
			(min1, node) = (self.res[0], 0)
			for j in range(N):
				if min1 < self.res[j]:
					(min1, node) = (self.res[j], j)
			self.temp[i] = min1
		return min(self.temp)

class Solution:

	def partyHouse(self, N, adj):

		def dfs(n, d, vis, res):
			vis.add(n)
			res[0] = max(res[0], d)
			for ech in adj[n]:
				if ech not in vis:
					dfs(ech, d + 1, vis, res)
		ans = 10 ** 10
		for i in range(1, N + 1):
			res = [0]
			vis = set()
			dfs(i, 0, vis, res)
			ans = min(ans, res[0])
		return ans


from collections import defaultdict

class Solution:

	def partyHouse(self, N, adj):
		g = defaultdict(list)
		for (i, nbrs) in enumerate(adj):
			for nbr in nbrs:
				g[i].append(nbr)
		dists = [-1] * (N + 1)

		def dfs(i, visited, d):
			if i not in visited:
				visited.add(i)
				dists[i] = max(dists[i], d)
				for nbr in g[i]:
					dfs(nbr, visited, d + 1)
		for n in range(1, N + 1):
			dfs(n, set(), 0)
		return min((d for d in dists if d != -1))


class Solution:

	def partyHouse(self, n, adj):
		n += 1
		g = [[] for _ in range(n)]
		for i in range(len(adj)):
			for j in adj[i]:
				g[i].append(j)

		def bfs(i):
			vis = [False for _ in range(n)]
			vis[i] = True
			lvl = [0 for _ in range(n)]
			q = [i]
			while q:
				for i in range(len(q)):
					t = q.pop(0)
					for i in g[t]:
						if not vis[i]:
							vis[i] = True
							lvl[i] = lvl[t] + 1
							q.append(i)
			return max(lvl)
		mx = 10000000
		for i in range(1, n):
			mx = min(mx, bfs(i))
		return mx


class Solution:

	def partyHouse(self, N, adj):
		res = 10 ** 10
		for i in range(1, N + 1):
			visited = [0 for _ in range(N + 1)]
			visited[i] = 1
			tmp1 = self.DFS(adj, visited, i, N)
			res = min(res, tmp1)
		return res

	def DFS(self, adj, visited, node, N):
		res = 0
		for x in adj[node]:
			if visited[x] == 1:
				continue
			visited[x] = 1
			res = max(res, 1 + self.DFS(adj, visited, x, N))
		return res


from collections import defaultdict

class Solution:

	def partyHouse(self, N, adj):
		d = defaultdict(list)
		for (k, v) in enumerate(adj):
			for i in v:
				d[k].append(i)
		distinct = [-1] * (N + 1)

		def helper(i, visit, val):
			if i not in visit:
				visit.add(i)
				distinct[i] = max(distinct[i], val)
				for j in d[i]:
					helper(j, visit, val + 1)
		for n in range(1, N + 1):
			helper(n, set(), 0)
		return min((o for o in distinct if o != -1))


class Solution:

	def partyHouse(self, n, adj):
		ans = [0]

		def dfs(x, adj, vis, d):
			vis[x] = 1
			ans[0] = max(ans[0], d)
			for i in adj[x]:
				if vis[i] == 0:
					dfs(i, adj, vis, d + 1)
		dis = 10 ** 10
		for i in range(1, n + 1):
			vis = [0] * (n + 1)
			ans[0] = 0
			dfs(i, adj, vis, 0)
			dis = min(dis, ans[0])
		return dis


class Solution:

	def partyHouse(self, N, adj):
		dist = [-1] * (N + 1)

		def dfs(curr, visited, d):
			if curr not in visited:
				visited.add(curr)
				dist[i] = max(dist[i], d)
				for ngbr in adj[curr]:
					dfs(ngbr, visited, d + 1)
		for i in range(1, N + 1):
			dfs(i, set(), 0)
		return min((d for d in dist if d >= 0))


class Solution:

	def partyHouse(self, N, adj):

		def dfs(start, distance, visited, res):
			visited.add(start)
			res[0] = max(distance, res[0])
			for neigh in adj[start]:
				if neigh not in visited:
					visited.add(neigh)
					dfs(neigh, distance + 1, visited, res)
		ans = N
		for i in range(1, N + 1):
			res = [0]
			visited = set()
			dfs(i, 0, visited, res)
			ans = min(ans, res[0])
		return ans


class Solution:

	def partyHouse(self, n, a):

		def dfs(s, c):
			nonlocal curr_max
			for j in a[s]:
				if not vis[j]:
					vis[j] = True
					dfs(j, c + 1)
			vis[s] = False
			curr_max = max(curr_max, c)
		vis = [False for _ in range(n + 1)]
		ans = float('inf')
		for i in range(1, n + 1):
			vis[i] = True
			curr_max = 0
			dfs(i, 0)
			ans = min(curr_max, ans)
		return ans


from collections import deque

def mgc(adj, i):
	Q = deque()
	Q.append(i)
	vis = set()
	vis.add(i)
	ans = 0
	while Q:
		ans += 1
		n = len(Q)
		for k in range(n):
			temp = Q.popleft()
			for j in adj[temp]:
				if j not in vis:
					Q.append(j)
					vis.add(j)
	return ans
from sys import maxsize

class Solution:

	def partyHouse(self, N, adj):
		ans = maxsize
		fans = None
		for i in range(1, N + 1):
			temp = mgc(adj, i)
			if temp < ans:
				ans = temp
		return ans - 1


class Solution:

	def partyHouse(self, N, adj):

		def bfs(adj, start):
			visit = [False] * (N + 1)
			q = [[start, 0]]
			dis = 0
			while q:
				val = q.pop(0)
				visit[val[0]] = True
				for v in adj[val[0]]:
					if visit[v] == False:
						dis = max(dis, val[1] + 1)
						q.append([v, val[1] + 1])
						visit[v] = True
			return dis
		ans = 999999999
		for i in range(1, N + 1):
			ans = min(ans, bfs(adj, i))
		return ans


import math

class Solution:

	def bfs(self, x, adj):
		q = [x]
		c = 0
		visited = set([x])
		while q:
			qs = len(q)
			for i in range(qs):
				n = q.pop(0)
				for j in adj[n]:
					if j not in visited:
						q.append(j)
						visited.add(j)
			if q:
				c += 1
		return c

	def partyHouse(self, N, adj):
		min_dist = math.inf
		for i in range(1, N + 1):
			min_dist = min(min_dist, self.bfs(i, adj))
		return min_dist


class Solution:

	def partyHouse(self, N, adj):
		min_height = N
		for i in range(1, N + 1):
			height = self.find_height(i, adj, 0)
			min_height = min(height, min_height)
		return min_height

	def find_height(self, curr, adj, pre):
		max_height = -1
		for w in adj[curr]:
			if w != pre:
				h = self.find_height(w, adj, curr)
				max_height = max(h, max_height)
		return max_height + 1


class Solution:

	def partyHouse(self, N, adj):
		(dist, depth) = self.find(1, [False] * (N + 1), adj)
		return dist + 1 >> 1

	def find(self, curr, vis, adj):
		dist = 0
		depth = 1
		vis[curr] = True
		for i in adj[curr]:
			if not vis[i]:
				(dist2, depth2) = self.find(i, vis, adj)
				dist = max(dist, dist2, depth + depth2 - 1)
				depth = max(depth, depth2 + 1)
		return (dist, depth)


class Solution:

	def partyHouse(self, N, adj):
		house = N + 1
		for i in range(1, N + 1):
			visited = [False] * (N + 1)
			visited[i] = True
			queue = [[i, 0]]
			dist = 0
			while queue:
				(cur, dis) = queue.pop(0)
				dist = max(dist, dis)
				for node in adj[cur]:
					if visited[node]:
						continue
					visited[node] = True
					queue.append([node, dis + 1])
			house = min(house, dist)
		return house


class Solution:

	def dfs(self, u, adj, visited):
		if u in visited:
			return 0
		visited[u] = True
		result = 1
		for v in adj[u]:
			r = self.dfs(v, adj, visited)
			if result < r + 1:
				result = r + 1
		return result

	def partyHouse(self, N, adj):
		self.inf = 10000000000.0
		result = self.inf
		for i in range(1, N + 1):
			r = self.dfs(i, adj, {})
			if r < result:
				result = r
		return result - 1


class Solution:

	def dfs(self, i, vis, d):
		self.md = max(self.md, d)
		vis[i] = True
		for k in self.adj[i]:
			if not vis[k]:
				self.dfs(k, vis, d + 1)

	def partyHouse(self, N, adj):
		mini = 10 ** 10
		self.adj = adj
		for i in range(1, N + 1):
			self.md = 0
			vis = [False] * (N + 1)
			self.dfs(i, vis, 0)
			mini = min(mini, self.md)
		return mini


class Solution:

	def max_distance(self, pos, adj, visited, distance):
		visited.add(pos)
		best = distance
		for house in adj[pos]:
			if house not in visited:
				best = max(best, self.max_distance(house, adj, visited, distance + 1))
		return best

	def partyHouse(self, N, adj):
		best = None
		for val in range(1, N):
			visited = set()
			if best == None:
				best = self.max_distance(val, adj, visited, 0)
			else:
				distance = self.max_distance(val, adj, visited, 0)
				if best > distance:
					best = distance
		return best


class Solution:
	currDist = 0

	def dfs(self, node, d, graph, visited):
		visited.add(node)
		self.currDist = max(self.currDist, d)
		for nbr in graph[node]:
			if nbr not in visited:
				self.dfs(nbr, d + 1, graph, visited)

	def partyHouse(self, N, adj):
		minDist = float('inf')
		for i in range(1, N + 1):
			visited = set()
			self.currDist = 0
			self.dfs(i, 0, adj, visited)
			minDist = min(self.currDist, minDist)
		return minDist


import sys

class Solution:

	def partyHouse(self, N, adj):
		graph = dict()
		for i in range(1, N + 1):
			for j in range(len(adj[i])):
				if i in graph:
					graph[i].append(adj[i][j])
				else:
					graph[i] = [adj[i][j]]

		def bfs(house):
			queue = [house]
			answer = 0
			distance = [sys.maxsize] * (N + 1)
			distance[house] = 0
			while queue:
				home = queue.pop(0)
				for neighbour in graph[home]:
					if distance[neighbour] == sys.maxsize:
						queue.append(neighbour)
						distance[neighbour] = distance[home] + 1
						answer = max(answer, distance[neighbour])
			return answer
		answer = sys.maxsize
		for i in range(1, N + 1):
			temp = bfs(i)
			if temp < answer:
				answer = temp
		return answer


class Solution:

	def partyHouse(self, N, adj):

		def dfs(curr, prev, dep):
			maxdep[0] = max(maxdep[0], dep)
			for edge in adj[curr]:
				if edge != prev:
					dfs(edge, curr, dep + 1)
		ans = 999999999
		for i in range(1, N + 1):
			maxdep = [0]
			dfs(i, -1, 0)
			ans = min(ans, maxdep[0])
		return ans


class Solution:

	def dfs(self, node, d, v, res, adj):
		v.add(node)
		res[0] = max(res[0], d)
		for i in adj[node]:
			if i not in v:
				self.dfs(i, d + 1, v, res, adj)

	def partyHouse(self, N, adj):
		ans = 10 ** 10
		for i in range(1, N + 1):
			res = [0]
			v = set()
			self.dfs(i, 0, v, res, adj)
			ans = min(ans, res[0])
		return ans


from collections import defaultdict

class Solution:

	def partyHouse(self, N, adj):
		d = defaultdict(list)
		for i in range(len(adj)):
			if adj[i]:
				p = i
			for j in adj[i]:
				d[i].append(j)

		def bfs(n):
			q = []
			q.append(n)
			s = set()
			s.add(n)
			k = 0
			while q:
				k += 1
				for i in range(len(q)):
					x = q.pop(0)
					for j in d[x]:
						if j not in s:
							s.add(j)
							q.append(j)
			return k - 1
		global ans
		vis = set()
		ans = float('inf')

		def dfs(n):
			global ans
			vis.add(n)
			ans = min(bfs(n), ans)
			for i in d[n]:
				if i not in vis:
					dfs(i)
		dfs(p)
		return ans


class Solution:

	def partyHouse(self, N, adj):
		rans = [float('inf')] * (N + 1)
		from collections import deque
		for start in range(1, N + 1):
			cur = -float('inf')
			vis = [False] * (N + 1)
			st = deque()
			st.append((start, 0))
			while st:
				(u, dis) = st.pop()
				if not vis[u]:
					vis[u] = True
					cur = max(cur, dis)
					for v in adj[u]:
						st.appendleft((v, dis + 1))
			rans[start] = cur
		return min(rans)


class Solution:

	def dfs(self, node, visited, dist):
		if dist <= self.ans and node not in visited:
			visited.add(node)
			self.node_distances[node] = min(self.node_distances[node], dist)
			for neighbor in self.adj_list[node]:
				if neighbor not in visited:
					self.dfs(neighbor, visited, dist + 1)
			visited.remove(node)

	def partyHouse(self, N, adj):
		self.adj_list = adj
		self.ans = N
		for node in range(1, N + 1):
			visited = set()
			self.node_distances = {idx + 1: N for idx in range(N)}
			self.dfs(node, visited, 0)
			self.ans = min(self.ans, max(self.node_distances.values()))
		return self.ans


class Solution:

	def partyHouse(self, N, adj):
		ans = 99999999999
		for i in range(1, N + 1):
			st = [[i, 0]]
			vis = set()
			temp = 0
			while st:
				(a, b) = st.pop()
				vis.add(a)
				temp = max(temp, b)
				for j in adj[a]:
					if j not in vis:
						st.append([j, b + 1])
			ans = min(ans, temp)
		return ans


from math import inf

class Solution:

	def partyHouse(self, N, adj):

		def dfs(n, d, vis, res):
			vis.add(n)
			res = max(res, d)
			for i in adj[n]:
				if i not in vis:
					res = dfs(i, d + 1, vis, res)
			return res
		ans = inf
		for i in range(1, N + 1):
			res = -inf
			vis = set()
			res = dfs(i, 0, vis, res)
			ans = min(ans, res)
		return ans


import math
from collections import deque

class Solution:

	def partyHouse(self, N, adj):
		longest = math.inf
		for i in range(1, N + 1):
			q = deque()
			q.append((i, 0))
			visited = [0 for j in range(N)]
			visited[i - 1] = 1
			distances = [-1 for j in range(N)]
			while q:
				(node, d) = q.popleft()
				distances[node - 1] = d
				for j in adj[node]:
					if not visited[j - 1]:
						visited[j - 1] = 1
						q.append((j, d + 1))
			longest = min(longest, max(distances))
		return longest


class Solution:

	def partyHouse(self, N, graph):
		min_height = float('inf')
		graph.pop(0)
		for edges in graph:
			for i in range(len(edges)):
				edges[i] -= 1

		def max_height(node, parent=None):
			height = 0
			for nei in graph[node]:
				if nei != parent:
					height = max(height, 1 + max_height(nei, node))
			return height
		for node in range(N):
			min_height = min(min_height, max_height(node))
		return min_height


class Solution:

	def partyHouse(self, N, adj):

		def dfs(adj, vis, v, d, res):
			if v not in vis:
				vis.add(v)
				res[0] = max(res[0], d)
			for e in adj[v]:
				if e not in vis:
					dfs(adj, vis, e, d + 1, res)
		mini = 1000000
		for i in range(1, N + 1):
			vis = set()
			res = [0]
			dfs(adj, vis, i, 0, res)
			if res[0] < mini:
				mini = res[0]
		return mini


class Solution:

	def partyHouse(self, N, adj):

		def dfs(currentNode, parentNode, curDist):
			tempAns = curDist
			for child in adj[currentNode]:
				if child != parentNode:
					tempAns = max(dfs(child, currentNode, curDist + 1), tempAns)
			return tempAns
		ans = 10 ** 9 + 7
		for j in range(1, N):
			temp = dfs(j, -1, 0)
			ans = min(temp, ans)
		return ans


class Solution:

	def partyHouse(self, n, adj):

		def dfs(i, prev, cost):
			mx[0] = max(mx[0], cost)
			for e in adj[i]:
				if e != prev:
					dfs(e, i, cost + 1)
		ans = 1000
		for i in range(1, n + 1):
			mx = [0]
			dfs(i, -1, 0)
			ans = min(ans, mx[0])
		return ans


class Solution:

	def partyHouse(self, N, adj):

		def dfs(node, par, dis):
			visited[node] = True
			self.maxd = max(self.maxd, dis)
			for nei in adj[node]:
				if visited[nei] == False:
					dfs(nei, node, dis + 1)
			return self.maxd
		mindis = float('inf')
		for i in range(1, N + 1):
			self.maxd = 0
			visited = [False] * (N + 1)
			dfs(i, -1, 0)
			mindis = min(mindis, self.maxd)
		return mindis


from collections import deque

class Solution:

	def dijkstra(self, V, adj, S):
		ans = [float('inf')] * (V + 1)
		ans[S] = 0
		queue = deque()
		queue.append(S)
		while queue:
			v = queue.popleft()
			for node in adj[v]:
				if ans[v] + 1 < ans[node]:
					ans[node] = ans[v] + 1
					queue.append(node)
		return max(ans[1:])

	def partyHouse(self, N, adj):
		minm = N
		for i in range(1, N):
			minm = min(self.dijkstra(N, adj, i), minm)
		return minm


class Solution:

	def partyHouse(self, N, adj):

		def dfs(curr, prev, dep):
			maxDep[0] = max(maxDep[0], dep)
			for e in adj[curr]:
				if e != prev:
					dfs(e, curr, dep + 1)
		ans = float('inf')
		for i in range(1, N + 1):
			maxDep = [0]
			dfs(i, -1, 0)
			ans = min(ans, maxDep[0])
		return ans


class Solution:

	def do_dfs(self, i, vis, d):
		self.Mx = max(self.Mx, d)
		vis[i] = True
		for v in self.adj[i]:
			if not vis[v]:
				self.do_dfs(v, vis, d + 1)

	def partyHouse(self, N, adj):
		self.adj = adj
		Min = 2 ** 63 + 7
		for i in range(1, N + 1):
			vis = [False] * (N + 1)
			self.Mx = 0
			self.do_dfs(i, vis, 0)
			Min = min(Min, self.Mx)
		return Min