from typing import List
from collections import defaultdict, deque


class Solution:
    """
    ## 269. Alien Dictionary

    There is a new alien language that uses the English alphabet. However, the order among the
    letters is unknown to you.

    You are given a list of strings `words` from the alien language's dictionary, where the
    strings in `words` are **sorted lexicographically** by the rules of this new language.

    Return a string of the unique letters in the new alien language sorted in the order they
    appear in the alien language. If there is no solution, return `""`. If there are multiple
    solutions, return **any of them**.

    ---

    ### Examples

    ```text
    Input:  words = ["wrt","wrf","er","ett","rftt"]
    Output: "wertf"

    Input:  words = ["z","x"]
    Output: "zx"

    Input:  words = ["z","x","z"]
    Output: ""
    Explanation: The order is invalid, so return "".
    ```

    ---

    ### Constraints

    - `1 <= words.length <= 100`
    - `1 <= words[i].length <= 100`
    - `words[i]` consists of only lowercase English letters.
    """

    def alienOrder(self, words: List[str]) -> str:
        # Compare adjacent words to extract character ordering constraints
        # Build directed graph of char dependencies; topological sort gives the order
        # Return '' if cycle detected (contradictory ordering)
        # O(C) — Kahn's BFS topological sort, C = total characters across all words
        adj = defaultdict(set)
        in_degree = {c: 0 for word in words for c in word}

        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            min_len = min(len(w1), len(w2))
            if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
                return ""
            for j in range(min_len):
                if w1[j] != w2[j]:
                    if w2[j] not in adj[w1[j]]:
                        adj[w1[j]].add(w2[j])
                        in_degree[w2[j]] += 1
                    break

        q = deque([c for c in in_degree if in_degree[c] == 0])
        result = []
        while q:
            c = q.popleft()
            result.append(c)
            for nb in adj[c]:
                in_degree[nb] -= 1
                if in_degree[nb] == 0:
                    q.append(nb)

        return "".join(result) if len(result) == len(in_degree) else ""

    def alienOrder_dfs(self, words: List[str]) -> str:
        # DFS topological sort with 3-state coloring: unvisited/in-progress/done
        # Cycle = revisiting an in-progress node; append to result in post-order
        # O(C) — DFS topological sort with cycle detection
        adj = defaultdict(set)
        chars = {c for word in words for c in word}

        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            min_len = min(len(w1), len(w2))
            if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
                return ""
            for j in range(min_len):
                if w1[j] != w2[j]:
                    adj[w1[j]].add(w2[j])
                    break

        # 0=unvisited, 1=visiting, 2=visited
        state = {c: 0 for c in chars}
        result = []

        def dfs(c: str) -> bool:
            if state[c] == 1:
                return False  # cycle
            if state[c] == 2:
                return True
            state[c] = 1
            for nb in adj[c]:
                if not dfs(nb):
                    return False
            state[c] = 2
            result.append(c)
            return True

        for c in chars:
            if state[c] == 0:
                if not dfs(c):
                    return ""

        return "".join(reversed(result))


if __name__ == '__main__':
    s = Solution()
    # BFS
    assert s.alienOrder(["wrt", "wrf", "er", "ett", "rftt"]) == "wertf"
    assert s.alienOrder(["z", "x"]) == "zx"
    assert s.alienOrder(["z", "x", "z"]) == ""

    # DFS (multiple valid orderings possible; check length and no cycle)
    res = s.alienOrder_dfs(["wrt", "wrf", "er", "ett", "rftt"])
    assert len(res) == 5
    assert s.alienOrder_dfs(["z", "x", "z"]) == ""

    print("All tests passed.")

"""
# Articulation Points (Tarjan's Algorithm)

Find all vertices whose removal increases the number of connected components
of an undirected graph.

## Examples
```text
Input: n=5, edges=[[0,1],[1,2],[2,0],[1,3],[3,4]]
Output: [1,3]
# Removing node 1 disconnects {0,2} from {3,4}; removing node 3 disconnects {4}.
```

## Constraints
- Non-root node u is an articulation point if some child v has low[v] >= disc[u]
- Root node is an articulation point if it has 2+ children in the DFS tree
- Graph may be disconnected; run DFS from every unvisited node
"""
from typing import List

class Solution:
    # Tarjan's articulation points:
    # node u is AP if: (1) root with 2+ children, OR (2) non-root with low[v] >= disc[u]
    def articulationPoints(self, n: int, edges: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(n)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        disc = [-1] * n
        low = [0] * n
        timer = [0]
        is_ap = [False] * n

        def dfs(node, parent):
            disc[node] = low[node] = timer[0]
            timer[0] += 1
            children = 0
            for neighbor in graph[node]:
                if disc[neighbor] == -1:
                    children += 1
                    dfs(neighbor, node)
                    low[node] = min(low[node], low[neighbor])
                    # non-root AP condition
                    if parent != -1 and low[neighbor] >= disc[node]:
                        is_ap[node] = True
                    # root AP condition: root is AP if it has 2+ children in DFS tree
                    if parent == -1 and children > 1:
                        is_ap[node] = True
                elif neighbor != parent:
                    low[node] = min(low[node], disc[neighbor])

        for i in range(n):
            if disc[i] == -1:
                dfs(i, -1)

        return [i for i in range(n) if is_ap[i]]


if __name__ == "__main__":
    sol = Solution()

    # Example from README: node 1 and node 3 are articulation points
    assert sol.articulationPoints(5, [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4]]) == [1, 3]

    # Simple bridge: 0-1-2 in a line, both endpoints' middle is AP
    assert sol.articulationPoints(3, [[0, 1], [1, 2]]) == [1]

    # Triangle (cycle) → no articulation points
    assert sol.articulationPoints(3, [[0, 1], [1, 2], [2, 0]]) == []

    # Single node, no edges → no articulation points
    assert sol.articulationPoints(1, []) == []

    print("All tests passed.")

"""
# LC 1192: Critical Connections in a Network (Bridges)

Find all edges whose removal increases the number of connected components
(bridges) of an undirected graph.

## Examples
```text
Input: n=4, connections=[[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
# 0-1-2 form a cycle (no bridge among them); edge (1,3) is a bridge.
```

## Constraints
- Edge (u,v) is a bridge if low[v] > disc[u]
- Pass parent to avoid treating the tree edge back to parent as a back edge
- Graph may be disconnected; run DFS from every unvisited node
"""
from typing import List

class Solution:
    # Tarjan's bridge finding: edge (u,v) is bridge if low[v] > disc[u]
    # low[v] = min discovery time reachable from subtree of v (excluding parent edge)
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        graph = [[] for _ in range(n)]
        for u, v in connections:
            graph[u].append(v)
            graph[v].append(u)

        disc = [-1] * n   # discovery time
        low = [0] * n     # lowest disc reachable
        timer = [0]
        bridges = []

        def dfs(node, parent):
            disc[node] = low[node] = timer[0]
            timer[0] += 1
            for neighbor in graph[node]:
                if disc[neighbor] == -1:  # unvisited
                    dfs(neighbor, node)
                    low[node] = min(low[node], low[neighbor])
                    if low[neighbor] > disc[node]:
                        bridges.append([node, neighbor])  # bridge found
                elif neighbor != parent:  # back edge (not to direct parent)
                    low[node] = min(low[node], disc[neighbor])

        for i in range(n):
            if disc[i] == -1:
                dfs(i, -1)

        return bridges


if __name__ == "__main__":
    sol = Solution()

    def norm(bridges):
        # normalize: sort each edge, then sort the list (order not deterministic)
        return sorted(sorted(edge) for edge in bridges)

    # Example from README: only edge (1,3) is a bridge
    assert norm(sol.criticalConnections(4, [[0, 1], [1, 2], [2, 0], [1, 3]])) == [[1, 3]]

    # A path 0-1-2-3: every edge is a bridge
    assert norm(sol.criticalConnections(4, [[0, 1], [1, 2], [2, 3]])) == [[0, 1], [1, 2], [2, 3]]

    # Triangle cycle: no bridges
    assert norm(sol.criticalConnections(3, [[0, 1], [1, 2], [2, 0]])) == []

    print("All tests passed.")

from typing import List
from collections import defaultdict, deque


class Solution:
    """
    ## 2392. Build a Matrix With Conditions

    You are given a positive integer `k`. You are also given:
    - a 2D integer array `rowConditions` of size `n` where `rowConditions[i] = [above_i, below_i]`,
      meaning row of `above_i` must appear **above** row of `below_i`.
    - a 2D integer array `colConditions` of size `m` where `colConditions[i] = [left_i, right_i]`,
      meaning column of `left_i` must appear to the **left** of column of `right_i`.

    The matrix contains each of the integers from `1` to `k` exactly once. Return **any** matrix
    of size `k x k` satisfying the conditions. If no answer exists, return an empty matrix.

    ---

    ### Examples

    ```text
    Input:  k=3, rowConditions=[[1,2],[3,2]], colConditions=[[2,1],[3,2]]
    Output: [[3,0,0],[0,0,1],[0,2,0]]

    Input:  k=3, rowConditions=[[1,2],[2,3],[3,1]], colConditions=[[1,2]]
    Output: []
    Explanation: Row conditions form a cycle.
    ```

    ---

    ### Constraints

    - `2 <= k <= 400`
    - `1 <= rowConditions.length, colConditions.length <= 10^4`
    - `rowConditions[i].length == colConditions[i].length == 2`
    - `1 <= above_i, below_i, left_i, right_i <= k`
    - `above_i != below_i`
    - `left_i != right_i`
    """

    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        # Topological sort row conditions to get row order, col conditions for col order
        # Place each number at (row_pos[num], col_pos[num]) in the k×k matrix
        # Return empty if either topological sort detects a cycle
        # O(k + conditions) — Kahn's BFS topological sort for rows and columns independently
        def topo_sort(conditions: List[List[int]]) -> List[int]:
            adj = defaultdict(list)
            in_deg = defaultdict(int)
            nodes = set(range(1, k + 1))
            for u, v in conditions:
                adj[u].append(v)
                in_deg[v] += 1
                nodes.add(u)
                nodes.add(v)
            q = deque([node for node in range(1, k + 1) if in_deg[node] == 0])
            order = []
            while q:
                node = q.popleft()
                order.append(node)
                for nb in adj[node]:
                    in_deg[nb] -= 1
                    if in_deg[nb] == 0:
                        q.append(nb)
            return order if len(order) == k else []

        row_order = topo_sort(rowConditions)
        col_order = topo_sort(colConditions)
        if not row_order or not col_order:
            return []

        row_pos = {val: i for i, val in enumerate(row_order)}
        col_pos = {val: i for i, val in enumerate(col_order)}

        matrix = [[0] * k for _ in range(k)]
        for val in range(1, k + 1):
            matrix[row_pos[val]][col_pos[val]] = val
        return matrix


if __name__ == '__main__':
    s = Solution()

    res = s.buildMatrix(3, [[1, 2], [3, 2]], [[2, 1], [3, 2]])
    assert len(res) == 3 and len(res[0]) == 3
    # Verify each number 1-3 appears exactly once
    flat = [x for row in res for x in row]
    assert sorted(x for x in flat if x != 0) == [1, 2, 3]

    # Cycle in row conditions -> empty
    assert s.buildMatrix(3, [[1, 2], [2, 3], [3, 1]], [[1, 2]]) == []

    print("All tests passed.")

from typing import List
import heapq
from collections import defaultdict


class Solution:
    """
    ## 787. Cheapest Flights Within K Stops

    There are `n` cities connected by some number of flights. You are given an array `flights`
    where `flights[i] = [from_i, to_i, price_i]` indicates that there is a flight from city
    `from_i` to city `to_i` with cost `price_i`.

    Given three integers `src`, `dst`, and `k`, return the **cheapest price** from `src` to `dst`
    with at most `k` stops. If there is no such route, return `-1`.

    ---

    ### Examples

    ```text
    Input:  n=4, flights=[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src=0, dst=3, k=1
    Output: 700
    Explanation: 0 -> 1 -> 3 costs 700.

    Input:  n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=1
    Output: 200

    Input:  n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=0
    Output: 500
    ```

    ---

    ### Constraints

    - `1 <= n <= 100`
    - `0 <= flights.length <= n * (n - 1) / 2`
    - `flights[i].length == 3`
    - `0 <= from_i, to_i < n`
    - `from_i != to_i`
    - `1 <= price_i <= 10^4`
    - There will not be any multiple flights between two cities.
    - `0 <= k <= n`
    """

    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        # Bellman-Ford with k+1 relaxation rounds (k stops = k+1 edges)
        # Use a copy of prices each round to prevent using more than one edge per round
        # O(k*E) — Bellman-Ford limited to k+1 relaxation rounds
        prices = [float('inf')] * n
        prices[src] = 0

        for _ in range(k + 1):
            tmp = prices[:]
            for u, v, w in flights:
                if prices[u] + w < tmp[v]:
                    tmp[v] = prices[u] + w
            prices = tmp

        return prices[dst] if prices[dst] < float('inf') else -1

    def findCheapestPrice_dijkstra(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        # O(V*E) — modified Dijkstra tracking stops; heap entry: (cost, node, stops_used)
        graph = defaultdict(list)
        for u, v, w in flights:
            graph[u].append((v, w))

        # dist[node][stops] = min cost
        dist = [[float('inf')] * (k + 2) for _ in range(n)]
        dist[src][0] = 0
        heap = [(0, src, 0)]  # (cost, node, stops)

        while heap:
            cost, u, stops = heapq.heappop(heap)
            if u == dst:
                return cost
            if stops > k:
                continue
            for v, w in graph[u]:
                new_cost = cost + w
                if new_cost < dist[v][stops + 1]:
                    dist[v][stops + 1] = new_cost
                    heapq.heappush(heap, (new_cost, v, stops + 1))

        return -1


if __name__ == '__main__':
    s = Solution()
    assert s.findCheapestPrice(4, [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], 0, 3, 1) == 700
    assert s.findCheapestPrice(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 1) == 200
    assert s.findCheapestPrice(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 0) == 500

    assert s.findCheapestPrice_dijkstra(4, [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], 0, 3, 1) == 700
    assert s.findCheapestPrice_dijkstra(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 1) == 200
    assert s.findCheapestPrice_dijkstra(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 0) == 500

    print("All tests passed.")

"""
# LC 1334: Find the City With the Smallest Number of Neighbors at a Threshold Distance

Find the city that has the fewest other cities reachable within
`distanceThreshold`. On a tie, return the city with the largest index.

## Examples
```text
Input: n=4, edges=[[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold=4
Output: 3
# City 3 reaches {1,2} (2 cities), the smallest count.
```

## Constraints
- Weighted undirected graph; use Floyd-Warshall all-pairs shortest paths — O(n^3)
- Tie-break toward the larger index (use <= when comparing counts)
- Unreachable pairs remain at infinity
"""
from typing import List

class Solution:
    # Floyd-Warshall: compute all-pairs shortest paths, then count reachable cities
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        INF = float('inf')
        dist = [[INF] * n for _ in range(n)]

        for i in range(n):
            dist[i][i] = 0  # distance to self is 0

        for u, v, w in edges:
            dist[u][v] = w
            dist[v][u] = w

        # relax all pairs through intermediate node k
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dist[i][k] + dist[k][j] < dist[i][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]

        # find city with fewest reachable neighbors within threshold
        # tie-break: pick the city with larger index
        best_city, min_count = -1, INF
        for i in range(n):
            count = sum(1 for j in range(n) if i != j and dist[i][j] <= distanceThreshold)
            if count <= min_count:  # <= ensures we pick larger index on tie
                min_count = count
                best_city = i

        return best_city


if __name__ == "__main__":
    sol = Solution()

    # Example from README
    assert sol.findTheCity(4, [[0, 1, 3], [1, 2, 1], [1, 3, 4], [2, 3, 1]], 4) == 3

    # LC classic example: threshold 2 → city 0 has fewest, tie broken by larger index
    assert sol.findTheCity(5, [[0, 1, 2], [0, 4, 8], [1, 2, 3], [1, 4, 2], [2, 3, 1], [3, 4, 1]], 2) == 0

    # Two isolated cities, threshold 0 → each reaches nobody, pick larger index
    assert sol.findTheCity(2, [], 0) == 1

    print("All tests passed.")

from typing import List


class Solution:
    """
    ## 1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

    Given a weighted undirected connected graph with `n` vertices numbered from `0` to `n - 1`,
    and an array `edges` where `edges[i] = [ai, bi, weighti]` represents a bidirectional and
    weighted edge between nodes `ai` and `bi`.

    A minimum spanning tree (MST) is a subset of the graph's edges that connects all vertices
    without cycles and with the minimum possible total edge weight.

    Find all the **critical** and **pseudo-critical** edges in the given graph's MST.

    - An MST edge whose deletion from the graph would cause the MST weight to increase is called
      a **critical edge**.
    - A **pseudo-critical edge** is one that can appear in some MSTs but not all.

    Return a list of two lists: the first list contains the indices of all critical edges, and
    the second list contains the indices of all pseudo-critical edges.

    ---

    ### Examples

    ```text
    Input:  n=5, edges=[[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
    Output: [[0,1],[2,3,4,5]]

    Input:  n=4, edges=[[0,1,1],[1,2,1],[0,2,1],[2,3,1]]
    Output: [[3],[0,1,2]]
    ```

    ---

    ### Constraints

    - `2 <= n <= 100`
    - `1 <= edges.length <= min(200, n * (n - 1) / 2)`
    - `edges[i].length == 3`
    - `0 <= ai < bi < n`
    - `1 <= weighti <= 1000`
    - All pairs `(ai, bi)` are distinct.
    """

    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        # Critical edge: removing it increases MST weight
        # Pseudo-critical: forcing it in doesn't increase MST weight
        # Use Kruskal's MST as baseline; test each edge by exclusion/inclusion
        # O(E^2 * alpha(n)) — Kruskal's with per-edge inclusion/exclusion to find base MST weight
        indexed = [(w, u, v, i) for i, (u, v, w) in enumerate(edges)]
        indexed.sort()

        def make_uf():
            parent = list(range(n))
            rank = [0] * n
            return parent, rank

        def find(parent, x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(parent, rank, x, y):
            px, py = find(parent, x), find(parent, y)
            if px == py:
                return False
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1
            return True

        def kruskal(skip_idx=-1, force_idx=-1):
            parent, rank = make_uf()
            weight = 0
            cnt = 0
            if force_idx != -1:
                w, u, v, _ = indexed[force_idx]
                union(parent, rank, u, v)
                weight += w
                cnt += 1
            for i, (w, u, v, orig) in enumerate(indexed):
                if i == skip_idx:
                    continue
                if union(parent, rank, u, v):
                    weight += w
                    cnt += 1
            return weight if cnt == n - 1 else float('inf')

        base = kruskal()
        critical, pseudo = [], []

        for i in range(len(indexed)):
            # Critical: removing raises MST weight
            if kruskal(skip_idx=i) > base:
                critical.append(indexed[i][3])
            # Pseudo-critical: forcing inclusion keeps same MST weight
            elif kruskal(force_idx=i) == base:
                pseudo.append(indexed[i][3])

        return [sorted(critical), sorted(pseudo)]


if __name__ == '__main__':
    s = Solution()
    res = s.findCriticalAndPseudoCriticalEdges(
        5, [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
    )
    assert res == [[0, 1], [2, 3, 4, 5]], res

    res2 = s.findCriticalAndPseudoCriticalEdges(4, [[0,1,1],[1,2,1],[0,2,1],[2,3,1]])
    assert res2 == [[3], [0, 1, 2]], res2

    print("All tests passed.")

from typing import List
import math


class Solution:
    """
    ## 2709. Greatest Common Divisor Traversal

    You are given a **0-indexed** integer array `nums`. There is an edge between two indices `i`
    and `j` if and only if `gcd(nums[i], nums[j]) > 1`.

    Return `true` if all the indices can be traversed (i.e., the graph is connected), or `false`
    otherwise.

    Note that a graph is connected if there is a path between every pair of vertices.

    ---

    ### Examples

    ```text
    Input:  nums = [2,3,6]
    Output: true
    Explanation: 2 and 6 share factor 2; 3 and 6 share factor 3. All connected.

    Input:  nums = [3,9,5]
    Output: false
    Explanation: 5 shares no factor with 3 or 9.

    Input:  nums = [4,3,12,8]
    Output: true
    ```

    ---

    ### Constraints

    - `1 <= nums.length <= 10^5`
    - `1 <= nums[i] <= 10^5`
    """

    def canTraverseAllPairs(self, nums: List[int]) -> bool:
        # Union-Find: connect indices that share a common prime factor
        # Factorize each number; union it with any previous number sharing a prime
        # All indices reachable iff they all belong to the same component
        # O(n * sqrt(max_val)) — Union-Find connecting indices via shared prime factors
        if len(nums) == 1:
            return True

        parent = list(range(len(nums) + 100001))  # indices 0..n-1, primes mapped to n+prime
        rank = [0] * (len(nums) + 100001)
        n = len(nums)

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(x: int, y: int) -> None:
            px, py = find(x), find(y)
            if px == py:
                return
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1

        prime_to_idx = {}  # first index that had this prime factor

        for i, num in enumerate(nums):
            val = num
            d = 2
            while d * d <= val:
                if val % d == 0:
                    if d in prime_to_idx:
                        union(i, prime_to_idx[d])
                    else:
                        prime_to_idx[d] = i
                    while val % d == 0:
                        val //= d
                d += 1
            if val > 1:
                if val in prime_to_idx:
                    union(i, prime_to_idx[val])
                else:
                    prime_to_idx[val] = i

        root = find(0)
        return all(find(i) == root for i in range(n))


if __name__ == '__main__':
    s = Solution()
    assert s.canTraverseAllPairs([2, 3, 6]) == True
    assert s.canTraverseAllPairs([3, 9, 5]) == False
    assert s.canTraverseAllPairs([4, 3, 12, 8]) == True
    assert s.canTraverseAllPairs([1]) == True
    assert s.canTraverseAllPairs([2, 2]) == True

    print("All tests passed.")

"""
# Kosaraju's Algorithm — Strongly Connected Components

Find all Strongly Connected Components (SCCs) in a directed graph. An SCC is a
maximal set of nodes where every node is reachable from every other node.

## Examples
```text
Input: n=5, edges=[[0,1],[1,2],[2,0],[1,3],[3,4]]
Output: [[0,1,2],[3],[4]]
# 0->1->2->0 form a cycle (one SCC); 3 and 4 are singletons.
```

## Constraints
- Two-pass DFS — O(V+E)
- Pass 1 records finish order on the original graph
- Pass 2 runs DFS on the transposed graph in reverse finish order
"""
from typing import List
from collections import defaultdict

class Solution:
    # Kosaraju's: 1) DFS on original, push to stack in finish order
    #             2) Transpose graph  3) DFS in reverse finish order on transposed
    def findSCCs(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        graph = defaultdict(list)
        rev_graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            rev_graph[v].append(u)

        visited = [False] * n
        stack = []

        def dfs1(node):
            visited[node] = True
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    dfs1(neighbor)
            stack.append(node)  # push after all descendants processed

        def dfs2(node, component):
            visited[node] = True
            component.append(node)
            for neighbor in rev_graph[node]:
                if not visited[neighbor]:
                    dfs2(neighbor, component)

        # Pass 1: fill stack with finish order
        for i in range(n):
            if not visited[i]:
                dfs1(i)

        # Pass 2: process in reverse finish order on transposed graph
        visited = [False] * n
        sccs = []
        while stack:
            node = stack.pop()
            if not visited[node]:
                component = []
                dfs2(node, component)
                sccs.append(sorted(component))

        return sccs


if __name__ == "__main__":
    sol = Solution()

    # SCC order in the outer list is not deterministic → compare sorted list of components
    assert sorted(sol.findSCCs(5, [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4]])) == [[0, 1, 2], [3], [4]]

    # Single cycle over all nodes → one SCC
    assert sorted(sol.findSCCs(3, [[0, 1], [1, 2], [2, 0]])) == [[0, 1, 2]]

    # DAG → every node is its own SCC
    assert sorted(sol.findSCCs(3, [[0, 1], [1, 2]])) == [[0], [1], [2]]

    print("All tests passed.")

"""
# LC 827: Making A Large Island

Flip at most one `0` to `1` in an n x n binary grid. Return the size of the
largest island (4-directionally connected group of 1s) after the flip.

## Examples
```text
Input: grid=[[1,0],[0,1]]
Output: 3
# Flipping the 0 at (0,1) (or (1,0)) bridges the two size-1 islands → size 3.
```

## Constraints
- Label + lookup — O(n^2)
- Label each island with a unique id (starting at 2) and record its size
- For each 0 cell, sum sizes of distinct neighboring islands + 1
- If the grid is all 1s (no 0 to flip), the answer is n^2
"""
from typing import List
from collections import defaultdict

class Solution:
    # Label each island with unique id, store sizes. For each 0, sum unique neighbor island sizes + 1.
    def largestIsland(self, grid: List[List[int]]) -> int:
        n = len(grid)
        island_id = 2  # start from 2 (0 and 1 are used)
        island_size = defaultdict(int)

        def dfs(r, c, iid):
            if r < 0 or r >= n or c < 0 or c >= n or grid[r][c] != 1:
                return 0
            grid[r][c] = iid  # label with island id
            return 1 + dfs(r+1,c,iid) + dfs(r-1,c,iid) + dfs(r,c+1,iid) + dfs(r,c-1,iid)

        # label all islands and record their sizes
        for r in range(n):
            for c in range(n):
                if grid[r][c] == 1:
                    island_size[island_id] = dfs(r, c, island_id)
                    island_id += 1

        # best without flipping (all 1s case)
        result = max(island_size.values(), default=0)

        # try flipping each 0
        for r in range(n):
            for c in range(n):
                if grid[r][c] == 0:
                    seen = set()
                    size = 1  # the flipped cell itself
                    for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
                        nr, nc = r + dr, c + dc
                        if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] > 1:
                            iid = grid[nr][nc]
                            if iid not in seen:
                                size += island_size[iid]
                                seen.add(iid)
                    result = max(result, size)

        return result


if __name__ == "__main__":
    sol = Solution()

    # Example from README (solution mutates grid, so pass a fresh copy each time)
    assert sol.largestIsland([[1, 0], [0, 1]]) == 3

    # Flipping the single 0 joins two halves → size 4
    assert sol.largestIsland([[1, 1], [1, 0]]) == 4

    # All ones, no 0 to flip → answer is n^2
    assert sol.largestIsland([[1, 1], [1, 1]]) == 4

    # All zeros → flip any one cell → island of size 1
    assert sol.largestIsland([[0, 0], [0, 0]]) == 1

    print("All tests passed.")

from typing import List
import heapq


class Solution:
    """
    ## 1584. Min Cost to Connect All Points

    You are given an array `points` representing integer coordinates of some points on a 2D plane,
    where `points[i] = [xi, yi]`.

    The cost of connecting two points `[xi, yi]` and `[xj, yj]` is the **Manhattan distance**
    between them: `|xi - xj| + |yi - yj|`.

    Return the minimum cost to make all points connected. All points are connected if there is
    exactly one simple path between any two points.

    ---

    ### Examples

    ```text
    Input:  points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
    Output: 20

    Input:  points = [[3,12],[-2,5],[-4,1]]
    Output: 18
    ```

    ---

    ### Constraints

    - `1 <= points.length <= 1000`
    - `-10^6 <= xi, yi <= 10^6`
    - All pairs `(xi, yi)` are distinct.
    """

    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        # Prim's MST: start from any node, greedily add cheapest edge to unvisited node
        # Manhattan distance is the edge weight between two points
        # O(n^2) — Prim's algorithm with visited set
        n = len(points)
        visited = set()
        heap = [(0, 0)]  # (cost, index)
        total = 0

        while len(visited) < n:
            cost, i = heapq.heappop(heap)
            if i in visited:
                continue
            visited.add(i)
            total += cost
            for j in range(n):
                if j not in visited:
                    dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
                    heapq.heappush(heap, (dist, j))

        return total

    def minCostConnectPoints_kruskal(self, points: List[List[int]]) -> int:
        # O(n^2 log n) — Kruskal's with Union-Find on all edges
        n = len(points)
        edges = []
        for i in range(n):
            for j in range(i + 1, n):
                dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
                edges.append((dist, i, j))
        edges.sort()

        parent = list(range(n))
        rank = [0] * n

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(x: int, y: int) -> bool:
            px, py = find(x), find(y)
            if px == py:
                return False
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1
            return True

        total, edges_used = 0, 0
        for dist, i, j in edges:
            if union(i, j):
                total += dist
                edges_used += 1
                if edges_used == n - 1:
                    break
        return total


if __name__ == '__main__':
    s = Solution()
    assert s.minCostConnectPoints([[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]) == 20
    assert s.minCostConnectPoints([[3, 12], [-2, 5], [-4, 1]]) == 18
    assert s.minCostConnectPoints([[0, 0]]) == 0

    assert s.minCostConnectPoints_kruskal([[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]) == 20
    assert s.minCostConnectPoints_kruskal([[3, 12], [-2, 5], [-4, 1]]) == 18

    print("All tests passed.")

"""
# LC 947: Most Stones Removed with Same Row or Column

A stone can be removed if it shares a row or column with another remaining
stone. Return the maximum number of stones that can be removed.

## Examples
```text
Input: stones=[[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
# All 6 stones form one connected component → remove 6 - 1 = 5.
```

## Constraints
- Union-Find grouping stones that share a row or column — O(n)
- Offset column indices to keep row and column keys in a shared namespace
- Answer = total_stones - number_of_components
"""
from typing import List

class Solution:
    # Union-Find: group stones sharing row or col. Each group can be reduced to 1 stone.
    # Answer = total_stones - number_of_groups
    def removeStones(self, stones: List[List[int]]) -> int:
        parent = {}

        def find(x):
            if x not in parent:
                parent[x] = x
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x, y):
            parent[find(x)] = find(y)

        for r, c in stones:
            # offset col by 10001 to avoid collision with row indices
            union(r, c + 10001)

        # count distinct components among stones
        components = len({find(r) for r, c in stones})
        return len(stones) - components


if __name__ == "__main__":
    sol = Solution()

    # Example from README: one big component → remove all but one
    assert sol.removeStones([[0, 0], [0, 1], [1, 0], [1, 2], [2, 1], [2, 2]]) == 5

    # LC example 2: two components → remove 5 - 2 = 3
    assert sol.removeStones([[0, 0], [0, 2], [1, 1], [2, 0], [2, 2]]) == 3

    # Single stone → nothing to remove
    assert sol.removeStones([[0, 0]]) == 0

    print("All tests passed.")

from typing import List
import heapq
from collections import defaultdict


class Solution:
    """
    ## 743. Network Delay Time

    You are given a network of `n` nodes, labeled from `1` to `n`. You are also given `times`,
    a list of travel times as directed edges `times[i] = (ui, vi, wi)`, where `ui` is the source
    node, `vi` is the target node, and `wi` is the time it takes for a signal to travel from
    source to target.

    We will send a signal from a given node `k`. Return the **minimum time** it takes for all
    the `n` nodes to receive the signal. If it is impossible for all the `n` nodes to receive
    the signal, return `-1`.

    ---

    ### Examples

    ```text
    Input:  times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
    Output: 2

    Input:  times = [[1,2,1]], n = 2, k = 1
    Output: 1

    Input:  times = [[1,2,1]], n = 2, k = 2
    Output: -1
    ```

    ---

    ### Constraints

    - `1 <= k <= n <= 100`
    - `1 <= times.length <= 6000`
    - `times[i].length == 3`
    - `1 <= ui, vi <= n`
    - `ui != vi`
    - `0 <= wi <= 100`
    - All pairs `(ui, vi)` are unique.
    """

    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        # Dijkstra from source k; shortest path to each node = signal arrival time
        # Answer is max of all shortest paths; -1 if any node unreachable
        # O((V+E)logV) — Dijkstra's single-source shortest path
        graph = defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))

        dist = {i: float('inf') for i in range(1, n + 1)}
        dist[k] = 0
        heap = [(0, k)]

        while heap:
            d, u = heapq.heappop(heap)
            if d > dist[u]:
                continue
            for v, w in graph[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    heapq.heappush(heap, (dist[v], v))

        ans = max(dist.values())
        return ans if ans < float('inf') else -1

    def networkDelayTime_bellman_ford(self, times: List[List[int]], n: int, k: int) -> int:
        # O(V*E) — Bellman-Ford relaxing all edges V-1 times
        dist = {i: float('inf') for i in range(1, n + 1)}
        dist[k] = 0

        for _ in range(n - 1):
            for u, v, w in times:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w

        ans = max(dist.values())
        return ans if ans < float('inf') else -1


if __name__ == '__main__':
    s = Solution()
    assert s.networkDelayTime([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2) == 2
    assert s.networkDelayTime([[1, 2, 1]], 2, 1) == 1
    assert s.networkDelayTime([[1, 2, 1]], 2, 2) == -1

    assert s.networkDelayTime_bellman_ford([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2) == 2
    assert s.networkDelayTime_bellman_ford([[1, 2, 1]], 2, 1) == 1
    assert s.networkDelayTime_bellman_ford([[1, 2, 1]], 2, 2) == -1

    print("All tests passed.")

"""
# LC 305: Number of Islands II

Given an m x n grid, add land cells one at a time from `positions`. After each
addition, return the current number of islands (4-directionally connected).

## Examples
```text
Input: m=3, n=3, positions=[[0,0],[0,1],[1,2],[2,1]]
Output: [1,1,2,3]
# (0,1) merges with (0,0); the last two additions are isolated.
```

## Constraints
- Online Union-Find with lazy initialization — O(k * alpha(mn))
- Encode a cell (r,c) as r*n + c
- Duplicate positions leave the island count unchanged
"""
from typing import List

class Solution:
    # Union-Find with lazy initialization - add land cells one by one
    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
        parent = {}
        rank = {}
        count = 0

        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x, y):
            nonlocal count
            px, py = find(x), find(y)
            if px == py:
                return
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1
            count -= 1  # merging two islands

        result = []
        for r, c in positions:
            cell = r * n + c
            if cell in parent:  # duplicate position
                result.append(count)
                continue

            parent[cell] = cell  # new island
            rank[cell] = 0
            count += 1

            for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
                nr, nc = r + dr, c + dc
                neighbor = nr * n + nc
                if 0 <= nr < m and 0 <= nc < n and neighbor in parent:
                    union(cell, neighbor)  # merge with adjacent land

            result.append(count)
        return result


if __name__ == "__main__":
    sol = Solution()

    # Example from README
    assert sol.numIslands2(3, 3, [[0, 0], [0, 1], [1, 2], [2, 1]]) == [1, 1, 2, 3]

    # LC classic example
    assert sol.numIslands2(3, 3, [[0, 0], [0, 1], [1, 2], [2, 1]]) == [1, 1, 2, 3]

    # Duplicate position leaves count unchanged
    assert sol.numIslands2(2, 2, [[0, 0], [0, 0], [1, 1]]) == [1, 1, 2]

    # Chain that eventually merges into one island
    assert sol.numIslands2(1, 3, [[0, 0], [0, 2], [0, 1]]) == [1, 2, 1]

    print("All tests passed.")

"""
# LC 1319: Number of Operations to Make Network Connected

Find the minimum number of cable moves needed to connect all `n` computers. A
cable can be reused from any redundant connection. Return -1 if impossible.

## Examples
```text
Input: n=4, connections=[[0,1],[0,2],[1,2]]
Output: 1
# Edge (1,2) is redundant; move it to connect the isolated computer 3.
```

## Constraints
- Union-Find — O(n + e)
- If len(connections) < n-1 → return -1 (not enough cables)
- Answer = number_of_components - 1
"""
from typing import List

class Solution:
    # Union-Find: count components and redundant edges
    # Need (components-1) moves; possible only if redundant_edges >= components-1
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n - 1:
            return -1  # not enough edges to connect n nodes

        parent = list(range(n))
        rank = [0] * n

        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x, y):
            px, py = find(x), find(y)
            if px == py:
                return False  # redundant edge
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1
            return True

        components = n
        for u, v in connections:
            if union(u, v):
                components -= 1  # merged two components

        return components - 1  # need this many moves to connect remaining components


if __name__ == "__main__":
    sol = Solution()

    # Example from README: one redundant edge, one isolated node
    assert sol.makeConnected(4, [[0, 1], [0, 2], [1, 2]]) == 1

    # LC example 2: two redundant edges cover two extra components
    assert sol.makeConnected(6, [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3]]) == 2

    # Not enough cables to ever connect n nodes
    assert sol.makeConnected(6, [[0, 1], [0, 2], [0, 3], [1, 2]]) == -1

    # Already fully connected → no moves needed
    assert sol.makeConnected(1, []) == 0

    print("All tests passed.")

"""
# LC 1976: Number of Ways to Arrive at Destination

Count the number of shortest paths from node `0` to node `n-1` in a weighted
undirected graph. Return the count modulo 10^9 + 7.

## Examples
```text
Input: n=7, roads=[[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],
                    [3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
Output: 4
# Four distinct paths achieve the minimum travel time.
```

## Constraints
- Dijkstra + path count — O((V+E) log V)
- Shorter path found → ways[v] = ways[u]; equal path → ways[v] += ways[u]
- Apply the modulo at every addition
"""
from typing import List
import heapq

class Solution:
    # Dijkstra + count: when we find a shorter path, reset count; equal path, add count
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        MOD = 10**9 + 7
        graph = [[] for _ in range(n)]
        for u, v, w in roads:
            graph[u].append((v, w))
            graph[v].append((u, w))

        dist = [float('inf')] * n
        ways = [0] * n
        dist[0] = 0
        ways[0] = 1  # one way to reach source

        heap = [(0, 0)]  # (distance, node)
        while heap:
            d, u = heapq.heappop(heap)
            if d > dist[u]:
                continue  # stale entry
            for v, w in graph[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    ways[v] = ways[u]  # new shortest path found, inherit count
                    heapq.heappush(heap, (dist[v], v))
                elif dist[u] + w == dist[v]:
                    ways[v] = (ways[v] + ways[u]) % MOD  # another equally short path

        return ways[n - 1]


if __name__ == "__main__":
    sol = Solution()

    # LC classic example: 4 shortest paths from 0 to 6
    assert sol.countPaths(7, [
        [0, 6, 7], [0, 1, 2], [1, 2, 3], [1, 3, 3], [6, 3, 3],
        [3, 5, 1], [6, 5, 1], [2, 5, 1], [0, 4, 5], [4, 6, 2],
    ]) == 4

    # Single edge → exactly one shortest path
    assert sol.countPaths(2, [[0, 1, 1]]) == 1

    # Two equal-length parallel routes 0->1->3 and 0->2->3
    assert sol.countPaths(4, [[0, 1, 1], [1, 3, 1], [0, 2, 1], [2, 3, 1]]) == 2

    print("All tests passed.")

from typing import List
from collections import deque
import heapq


class Solution:
    """
    ## 1631. Path With Minimum Effort

    You are a hiker preparing for an upcoming hike. You are given `heights`, a 2D array of size
    `rows x columns`, where `heights[row][col]` represents the height of cell `(row, col)`.
    You are situated in the top-left cell, `(0, 0)`, and you hope to travel to the bottom-right
    cell, `(rows-1, columns-1)`. You can move **up**, **down**, **left**, or **right**, and you
    wish to find the route that requires the minimum **effort**.

    The **effort** of a route is the maximum absolute difference in heights between two consecutive
    cells of the route.

    Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

    ---

    ### Examples

    ```text
    Input:  heights = [[1,2,2],[3,8,2],[5,3,5]]
    Output: 2
    Explanation: The route [1,3,5,3,5] has a maximum absolute difference of 2.

    Input:  heights = [[1,2,3],[3,8,4],[5,3,5]]
    Output: 1
    Explanation: The route [1,2,3,4,5] has a maximum absolute difference of 1.

    Input:  heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
    Output: 0
    ```

    ---

    ### Constraints

    - `rows == heights.length`
    - `cols == heights[i].length`
    - `1 <= rows, cols <= 100`
    - `1 <= heights[i][j] <= 10^6`
    """

    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        # Dijkstra: minimize the maximum absolute difference along the path
        # Priority queue stores (max_effort_so_far, row, col)
        # O(m*n*log(10^6)) — binary search on effort, BFS to validate
        rows, cols = len(heights), len(heights[0])
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        def can_reach(effort: int) -> bool:
            visited = [[False] * cols for _ in range(rows)]
            q = deque([(0, 0)])
            visited[0][0] = True
            while q:
                r, c = q.popleft()
                if r == rows - 1 and c == cols - 1:
                    return True
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc]:
                        if abs(heights[nr][nc] - heights[r][c]) <= effort:
                            visited[nr][nc] = True
                            q.append((nr, nc))
            return False

        lo, hi = 0, 10**6 - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if can_reach(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo

    def minimumEffortPath_dijkstra(self, heights: List[List[int]]) -> int:
        # O(m*n*log(m*n)) — Dijkstra treating effort as edge weight
        rows, cols = len(heights), len(heights[0])
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        effort = [[float('inf')] * cols for _ in range(rows)]
        effort[0][0] = 0
        heap = [(0, 0, 0)]  # (effort, row, col)

        while heap:
            e, r, c = heapq.heappop(heap)
            if r == rows - 1 and c == cols - 1:
                return e
            if e > effort[r][c]:
                continue
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    new_e = max(e, abs(heights[nr][nc] - heights[r][c]))
                    if new_e < effort[nr][nc]:
                        effort[nr][nc] = new_e
                        heapq.heappush(heap, (new_e, nr, nc))
        return effort[rows - 1][cols - 1]


if __name__ == '__main__':
    s = Solution()
    assert s.minimumEffortPath([[1, 2, 2], [3, 8, 2], [5, 3, 5]]) == 2
    assert s.minimumEffortPath([[1, 2, 3], [3, 8, 4], [5, 3, 5]]) == 1
    assert s.minimumEffortPath([[1, 2, 1, 1, 1], [1, 2, 1, 2, 1], [1, 2, 1, 2, 1], [1, 2, 1, 2, 1], [1, 1, 1, 2, 1]]) == 0

    assert s.minimumEffortPath_dijkstra([[1, 2, 2], [3, 8, 2], [5, 3, 5]]) == 2
    assert s.minimumEffortPath_dijkstra([[1, 2, 3], [3, 8, 4], [5, 3, 5]]) == 1

    print("All tests passed.")

from typing import List
from collections import defaultdict


class Solution:
    """
    ## 332. Reconstruct Itinerary

    You are given a list of airline `tickets` represented by pairs of departure and arrival
    airports `[from, to]`. Reconstruct the itinerary in order. All of the tickets must be used
    once and only once.

    The itinerary must begin with `"JFK"`. If there are multiple valid itineraries, return the
    itinerary that has the **smallest lexical order** when read as a single string.

    You may assume all tickets form at least one valid itinerary. You must use all the tickets.

    ---

    ### Examples

    ```text
    Input:  tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
    Output: ["JFK","MUC","LHR","SFO","SJC"]

    Input:  tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
    Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
    ```

    ---

    ### Constraints

    - `1 <= tickets.length <= 300`
    - `tickets[i].length == 2`
    - `from_i` and `to_i` consist of uppercase English letters.
    - `from_i != to_i`
    """

    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        # Hierholzer's algorithm for Eulerian path: DFS, add to result on backtrack
        # Sort destinations so lexicographically smallest path is found first
        # O(E^2) — DFS with backtracking on sorted adjacency lists
        graph = defaultdict(list)
        for src, dst in sorted(tickets, reverse=True):
            graph[src].append(dst)
        # Sort descending so we can pop from end (cheapest pop) in lex order
        for k in graph:
            graph[k].sort(reverse=True)

        result = []

        def dfs(airport: str) -> None:
            while graph[airport]:
                dfs(graph[airport].pop())
            result.append(airport)

        dfs("JFK")
        return result[::-1]

    def findItinerary_hierholzer(self, tickets: List[List[str]]) -> List[str]:
        # O(E log E) — Hierholzer's iterative Eulerian path
        graph = defaultdict(list)
        for src, dst in tickets:
            graph[src].append(dst)
        for k in graph:
            graph[k].sort(reverse=True)

        stack = ["JFK"]
        result = []
        while stack:
            while graph[stack[-1]]:
                stack.append(graph[stack[-1]].pop())
            result.append(stack.pop())
        return result[::-1]


if __name__ == '__main__':
    s = Solution()
    t1 = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
    assert s.findItinerary(t1) == ["JFK", "MUC", "LHR", "SFO", "SJC"]

    t2 = [["JFK", "SFO"], ["JFK", "ATL"], ["SFO", "ATL"], ["ATL", "JFK"], ["ATL", "SFO"]]
    assert s.findItinerary(t2) == ["JFK", "ATL", "JFK", "SFO", "ATL", "SFO"]

    t3 = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
    assert s.findItinerary_hierholzer(t3) == ["JFK", "MUC", "LHR", "SFO", "SJC"]

    print("All tests passed.")

"""
# LC 1091: Shortest Path in Binary Matrix

Find the length of the shortest clear path (cells with value `0`) from `(0,0)`
to `(n-1,n-1)` moving in 8 directions. Return -1 if no such path exists.

## Examples
```text
Input: grid=[[0,1],[1,0]]
Output: 2
# Move diagonally (0,0) -> (1,1); both cells are clear.
```

## Constraints
- BFS on an unweighted grid — O(n^2)
- 8-directional movement (includes diagonals)
- Return -1 if start or end cell is blocked (value 1)
"""
from typing import List
from collections import deque

class Solution:
    # BFS in 8 directions - first time we reach (n-1,n-1) is shortest path
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if grid[0][0] == 1 or grid[n-1][n-1] == 1:
            return -1  # start or end is blocked

        if n == 1:
            return 1  # single cell grid

        queue = deque([(0, 0, 1)])  # (row, col, path_length)
        grid[0][0] = 1  # mark visited by setting to 1

        while queue:
            r, c, dist = queue.popleft()
            for dr in [-1, 0, 1]:
                for dc in [-1, 0, 1]:
                    if dr == 0 and dc == 0:
                        continue
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                        if nr == n - 1 and nc == n - 1:
                            return dist + 1  # reached destination
                        grid[nr][nc] = 1  # mark visited
                        queue.append((nr, nc, dist + 1))

        return -1  # no path found


if __name__ == "__main__":
    sol = Solution()

    # Example from README (solution mutates grid, so pass a fresh copy each time)
    assert sol.shortestPathBinaryMatrix([[0, 1], [1, 0]]) == 2

    # Single clear cell → path length 1
    assert sol.shortestPathBinaryMatrix([[0]]) == 1

    # LC classic example: 3x3 shortest clear path
    assert sol.shortestPathBinaryMatrix([[0, 0, 0], [1, 1, 0], [1, 1, 0]]) == 4

    # Blocked start → no path
    assert sol.shortestPathBinaryMatrix([[1, 0], [0, 0]]) == -1

    print("All tests passed.")

from typing import List
from collections import deque
import heapq


class Solution:
    """
    ## 778. Swim in Rising Water

    You are given an `n x n` integer matrix `grid` where each value `grid[i][j]` represents the
    elevation at that point `(i, j)`.

    The rain starts to fall. At time `t`, the depth of the water everywhere is `t`. You can swim
    from a square to another 4-directionally adjacent square if and only if the elevation of both
    squares individually are at most `t`. You can swim infinite distances in zero time. Of course,
    you must stay within the boundaries of the grid during your swim.

    Return the least time until you can reach the bottom-right square `(n-1, n-1)` if you start
    at the top-left square `(0, 0)`.

    ---

    ### Examples

    ```text
    Input:  grid = [[0,2],[1,3]]
    Output: 3
    Explanation: At time 3, we can swim from (0,0) -> (0,1) -> (1,1).

    Input:  grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
    Output: 16
    ```

    ---

    ### Constraints

    - `n == grid.length == grid[i].length`
    - `1 <= n <= 50`
    - `0 <= grid[i][j] < n^2`
    - Each value `grid[i][j]` is unique.
    """

    def swimInWater(self, grid: List[List[int]]) -> int:
        # Dijkstra variant: minimize the maximum elevation on the path to (n-1, n-1)
        # Priority queue stores (max_elevation_so_far, row, col)
        # O(n^2 log n) — binary search on time t, BFS to check reachability
        n = len(grid)
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        def can_reach(t: int) -> bool:
            if grid[0][0] > t:
                return False
            visited = [[False] * n for _ in range(n)]
            visited[0][0] = True
            q = deque([(0, 0)])
            while q:
                r, c = q.popleft()
                if r == n - 1 and c == n - 1:
                    return True
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] <= t:
                        visited[nr][nc] = True
                        q.append((nr, nc))
            return False

        lo, hi = grid[0][0], n * n - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if can_reach(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo

    def swimInWater_dijkstra(self, grid: List[List[int]]) -> int:
        # O(n^2 log n) — min-heap treating max elevation on path as cost
        n = len(grid)
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        visited = [[False] * n for _ in range(n)]
        heap = [(grid[0][0], 0, 0)]

        while heap:
            t, r, c = heapq.heappop(heap)
            if visited[r][c]:
                continue
            visited[r][c] = True
            if r == n - 1 and c == n - 1:
                return t
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc]:
                    heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))
        return -1


if __name__ == '__main__':
    s = Solution()
    assert s.swimInWater([[0, 2], [1, 3]]) == 3
    assert s.swimInWater([[0, 1, 2, 3, 4], [24, 23, 22, 21, 5],
                          [12, 13, 14, 15, 16], [11, 17, 18, 19, 20], [10, 9, 8, 7, 6]]) == 16

    assert s.swimInWater_dijkstra([[0, 2], [1, 3]]) == 3
    assert s.swimInWater_dijkstra([[0, 1, 2, 3, 4], [24, 23, 22, 21, 5],
                                   [12, 13, 14, 15, 16], [11, 17, 18, 19, 20], [10, 9, 8, 7, 6]]) == 16

    print("All tests passed.")