Constraints

• 1 <= n <= 10^5
• edges has exactly n - 1 pairs
• The graph is guaranteed to be a tree (connected and acyclic)
• Nodes are labeled from 1 to n
• Return 0 for a single-node tree (no edges)

Examples

Solution

from collections import defaultdict, deque

def solution(n, edges):
    if n <= 1:
        return 0
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    def bfs(start):
        visited = {start}
        q = deque([(start, 0)])
        far_node, far_dist = start, 0
        while q:
            node, dist = q.popleft()
            if dist > far_dist:
                far_dist, far_node = dist, node
            for nxt in adj[node]:
                if nxt not in visited:
                    visited.add(nxt)
                    q.append((nxt, dist + 1))
        return far_node, far_dist

    a, _ = bfs(1)
    _, diameter = bfs(a)
    return diameter

Time complexity: O(n) — two BFS traversals over a tree with n nodes and n-1 edges.. Space complexity: O(n) — adjacency list, visited set, and BFS queue..

Hints

1. The diameter is the longest shortest-path between any two nodes. Brute-forcing all pairs is O(n^2) — too slow for n up to 1e5.
2. Key lemma: from ANY node, the farthest node found by BFS/DFS is guaranteed to be one endpoint of a diameter.
3. Run BFS twice: first from node 1 to find a farthest node `a`, then from `a` to find the farthest distance. That distance is the diameter.
4. Each BFS is O(n) on a tree, so the total is linear.

Constraints

• 1 <= n (grid is square, n x n)
• Each cell is 0 (free) or 1 (blocked)
• Movement is restricted to the four cardinal directions
• Return -1 if the start or end is blocked, or no path exists
• Steps count edges traversed; a 1x1 free grid returns 0

Examples

Solution

from collections import deque

def solution(grid):
    n = len(grid)
    if n == 0:
        return -1
    if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
        return -1
    visited = [[False] * n for _ in range(n)]
    visited[0][0] = True
    q = deque([(0, 0, 0)])
    while q:
        r, c, steps = q.popleft()
        if r == n - 1 and c == n - 1:
            return steps
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] == 0:
                visited[nr][nc] = True
                q.append((nr, nc, steps + 1))
    return -1

Time complexity: O(n^2) — each of the n*n cells is enqueued at most once.. Space complexity: O(n^2) — the visited matrix and the BFS queue..

Hints

1. With unit-cost moves, BFS finds the shortest path; DFS does not guarantee minimality.
2. Mark a cell visited at enqueue time (not dequeue) to avoid pushing it multiple times.
3. Check the start and end cells up front — if either is blocked, the answer is -1.
4. Track the step count alongside each cell in the queue, or do level-by-level BFS.

Constraints

• 1 <= n (grid is square, n x n)
• Each cell is 0 (free) or 1 (blocked)
• A simple path may not revisit any cell
• Movement is restricted to the four cardinal directions
• Return 0 if the start or end is blocked, or no path exists; a 1x1 free grid has exactly 1 path

Examples

Solution

def solution(grid):
    n = len(grid)
    if n == 0:
        return 0
    if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
        return 0
    visited = [[False] * n for _ in range(n)]
    count = 0

    def dfs(r, c):
        nonlocal count
        if r == n - 1 and c == n - 1:
            count += 1
            return
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] == 0:
                visited[nr][nc] = True
                dfs(nr, nc)
                visited[nr][nc] = False

    visited[0][0] = True
    dfs(0, 0)
    return count

Time complexity: O(4^(n^2)) in the worst case — there can be exponentially many simple paths, and each is enumerated explicitly.. Space complexity: O(n^2) for the visited matrix plus O(n^2) recursion depth (a simple path visits at most every cell once)..

Hints

1. This is exhaustive enumeration, not a shortest-path problem — DFS with backtracking is the natural fit.
2. Mark the current cell visited before recursing and UNMARK it after returning, so the cell is free for sibling branches.
3. Increment the counter only when you reach (n-1, n-1); do not stop early, since you want every path.
4. Because the count of simple paths grows exponentially with grid size, this only scales to small n — mention this limitation in an interview rather than claiming a polynomial bound.