Find the Closest Marked Node - Practice Coding Problems

Find the Closest Marked Node - Problem

You are given a positive integer n which is the number of nodes of a 0-indexed directed weighted graph and a 0-indexed 2D array edges where edges[i] = [ui, vi, wi] indicates that there is an edge from node ui to node vi with weight wi.

You are also given a node s and a node array marked; your task is to find the minimum distance from s to any of the nodes in marked.

Return an integer denoting the minimum distance from s to any node in marked or -1 if there are no paths from s to any of the marked nodes.

Input & Output

Example 1 — Basic Case

$ Input: n = 4, edges = [[0,1,5],[0,2,3],[1,3,2],[2,3,4]], s = 0, marked = [2,3]

› Output: 3

💡 Note: Shortest path from node 0 to any marked node: 0→2 has distance 3, 0→1→3 has distance 7, so minimum is 3

Example 2 — No Path Available

$ Input: n = 3, edges = [[0,1,2]], s = 0, marked = [2]

› Output: -1

💡 Note: No path exists from node 0 to marked node 2, so return -1

Example 3 — Source is Marked

$ Input: n = 2, edges = [[0,1,5]], s = 0, marked = [0]

› Output: 0

💡 Note: Source node 0 is itself marked, so distance is 0

Constraints

2 ≤ n ≤ 10⁵
1 ≤ edges.length ≤ 10⁵
edges[i].length == 3
0 ≤ u_i, v_i ≤ n - 1
1 ≤ w_i ≤ 10⁶
0 ≤ s ≤ n - 1
1 ≤ marked.length ≤ n

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Directed weighted graph with source node and marked destinations

Shortest Path Search

Use Dijkstra's algorithm to find minimum distances

Result

Return distance to closest marked node or -1 if unreachable

Key Takeaway

🎯 Key Insight: Use Dijkstra's algorithm with early termination - stop as soon as any marked destination is reached

Asked in

G Google 42 a Amazon 38 M Microsoft 31 f Meta 25

The key insight is to use Dijkstra's shortest path algorithm with early termination - stop as soon as we reach any marked node rather than computing shortest paths to all nodes. Build an adjacency list from edges, then use a priority queue to explore nodes in order of shortest distance. Best approach is Dijkstra's Algorithm with Time: O(E log V), Space: O(V + E).

Common Approaches

Approach	Time	Space	Notes
✓ Dijkstra's Algorithm	O(E log V)	O(V + E)	Use Dijkstra's shortest path algorithm with priority queue
Brute Force DFS	O(2ⁿ)	O(n)	Use DFS to explore all paths from source to each marked node

Dijkstra's Algorithm — Algorithm Steps

Build adjacency list from edges
Use priority queue to explore nodes by shortest distance
Return distance when first marked node is reached

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set distance to source as 0, all others as infinity

Process Queue

Extract minimum distance node from priority queue

Early Exit

Return distance when first marked node is reached

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_NODES 1000
#define MAX_EDGES 1000

typedef struct {
    int to, weight;
} Edge;

typedef struct {
    int dist, node;
} PQItem;

Edge graph[MAX_NODES][MAX_EDGES];
int graphSize[MAX_NODES];
int markedSet[MAX_NODES];
int dist[MAX_NODES];
PQItem pq[MAX_NODES * MAX_EDGES];
int pqSize;

void heapifyUp(int idx) {
    while (idx > 0) {
        int parent = (idx - 1) / 2;
        if (pq[parent].dist <= pq[idx].dist) break;
        PQItem temp = pq[parent];
        pq[parent] = pq[idx];
        pq[idx] = temp;
        idx = parent;
    }
}

void heapifyDown(int idx) {
    while (2 * idx + 1 < pqSize) {
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
        int smallest = idx;
        
        if (pq[left].dist < pq[smallest].dist) smallest = left;
        if (right < pqSize && pq[right].dist < pq[smallest].dist) smallest = right;
        
        if (smallest == idx) break;
        
        PQItem temp = pq[idx];
        pq[idx] = pq[smallest];
        pq[smallest] = temp;
        idx = smallest;
    }
}

void push(int d, int node) {
    pq[pqSize].dist = d;
    pq[pqSize].node = node;
    heapifyUp(pqSize++);
}

PQItem pop() {
    PQItem result = pq[0];
    pq[0] = pq[--pqSize];
    if (pqSize > 0) heapifyDown(0);
    return result;
}

int solution(int n, int edges[][3], int edgeCount, int s, int marked[], int markedCount) {
    memset(graphSize, 0, sizeof(graphSize));
    memset(markedSet, 0, sizeof(markedSet));
    
    for (int i = 0; i < edgeCount; i++) {
        int u = edges[i][0], v = edges[i][1], w = edges[i][2];
        graph[u][graphSize[u]].to = v;
        graph[u][graphSize[u]].weight = w;
        graphSize[u]++;
    }
    
    for (int i = 0; i < markedCount; i++) {
        markedSet[marked[i]] = 1;
    }
    
    for (int i = 0; i < n; i++) {
        dist[i] = INT_MAX;
    }
    dist[s] = 0;
    
    pqSize = 0;
    push(0, s);
    
    while (pqSize > 0) {
        PQItem curr = pop();
        int d = curr.dist, u = curr.node;
        
        if (markedSet[u]) {
            return d;
        }
        
        if (d > dist[u]) continue;
        
        for (int i = 0; i < graphSize[u]; i++) {
            int v = graph[u][i].to, w = graph[u][i].weight;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                push(dist[v], v);
            }
        }
    }
    
    return -1;
}

int main() {
    int n, s;
    scanf("%d", &n);
    
    // Simplified input parsing
    int edges[MAX_EDGES][3];
    int edgeCount = 0;
    
    scanf("%d", &s);
    
    int marked[MAX_NODES];
    int markedCount = 0;
    
    printf("%d\n", solution(n, edges, edgeCount, s, marked, markedCount));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(E log V)

Dijkstra's algorithm with priority queue operations

⚡ Linearithmic

Space Complexity

O(V + E)

Adjacency list storage plus priority queue and distance arrays

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dijkstra's Algorithm — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler