Time Taken to Mark All Nodes - Practice Coding Problems

Time Taken to Mark All Nodes - Problem

There exists an undirected tree with n nodes numbered 0 to n - 1. You are given a 2D integer array edges of length n - 1, where edges[i] = [ui, vi] indicates that there is an edge between nodes ui and vi in the tree.

Initially, all nodes are unmarked. For each node i:

If i is odd, the node will get marked at time x if there is at least one node adjacent to it which was marked at time x - 1.
If i is even, the node will get marked at time x if there is at least one node adjacent to it which was marked at time x - 2.

Return an array times where times[i] is the time when all nodes get marked in the tree, if you mark node i at time t = 0.

Note that the answer for each times[i] is independent, i.e. when you mark node i all other nodes are unmarked.

Input & Output

Example 1 — Simple Chain

$ Input: edges = [[0,1],[1,2]]

› Output: [4,2,3]

💡 Note: Starting from node 0: 0→1 (t=1) then 1→2 (t=3), max=3. Starting from node 1: 1→0 (t=2) and 1→2 (t=3), max=3. Starting from node 2: 2→1 (t=1) then 1→0 (t=3), max=3.

Example 2 — Single Edge

$ Input: edges = [[0,1]]

› Output: [1,2]

💡 Note: From node 0: mark node 1 at time 1 (odd). From node 1: mark node 0 at time 2 (even).

Example 3 — Star Graph

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

› Output: [2,2,2,2]

💡 Note: Node 1 connects to all others. From any node, the maximum time depends on the parity rules and distances.

Constraints

1 ≤ n ≤ 10⁵
edges.length == n - 1
0 ≤ u_i, v_i ≤ n - 1
The given input represents a valid tree.

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Undirected tree with nodes 0,1,2 connected linearly

Marking Rules

Odd nodes: +1 time, Even nodes: +2 time from marked neighbor

All Starting Points

Calculate max marking time for each possible starting node

Key Takeaway

🎯 Key Insight: Different marking speeds based on node parity create complex timing dependencies in tree traversal

Asked in

M Meta 8 G Google 5

The key insight is that different node parities create asymmetric spreading patterns in the tree. The optimal approach uses tree rerooting dynamic programming to avoid redundant BFS computations. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n²)	O(n)	Simulate BFS from each starting node independently
Tree Rerooting Dynamic Programming	O(n)	O(n)	Use tree rerooting to compute all answers efficiently

Brute Force Simulation — Algorithm Steps

For each node as starting point
Run BFS with timing rules
Track when all nodes are marked

Visualization

Tap to expand

Step-by-Step Walkthrough

Choose Start

Select a node as starting point (time 0)

BFS Spread

Apply timing rules: odd nodes +1, even nodes +2

Record Max

Track maximum time when all nodes are marked

Code -

solution.c — C

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

#define MAX_N 1000

int graph[MAX_N][MAX_N];
int graphSize[MAX_N];
int markedTime[MAX_N];
int queue[MAX_N];
int front, rear;

int* solution(int** edges, int edgesSize, int* edgesColSize, int* returnSize) {
    *returnSize = edgesSize + 1;
    int* result = (int*)malloc((*returnSize) * sizeof(int));
    
    if (edgesSize == 0) {
        result[0] = 0;
        *returnSize = 1;
        return result;
    }
    
    int n = edgesSize + 1;
    
    // Initialize graph
    for (int i = 0; i < n; i++) {
        graphSize[i] = 0;
    }
    
    // Build adjacency list
    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        graph[u][graphSize[u]++] = v;
        graph[v][graphSize[v]++] = u;
    }
    
    // For each starting node
    for (int start = 0; start < n; start++) {
        // Initialize marked times
        for (int i = 0; i < n; i++) {
            markedTime[i] = -1;
        }
        markedTime[start] = 0;
        
        // BFS
        front = rear = 0;
        queue[rear++] = start;
        int maxTime = 0;
        
        while (front < rear) {
            int node = queue[front++];
            int currentTime = markedTime[node];
            
            for (int i = 0; i < graphSize[node]; i++) {
                int neighbor = graph[node][i];
                if (markedTime[neighbor] == -1) {
                    int newTime = neighbor % 2 == 1 ? currentTime + 1 : currentTime + 2;
                    markedTime[neighbor] = newTime;
                    if (newTime > maxTime) maxTime = newTime;
                    queue[rear++] = neighbor;
                }
            }
        }
        
        result[start] = maxTime;
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for the format [[a,b],[c,d],...]
    int edges[MAX_N][2];
    int edgesSize = 0;
    
    if (strcmp(line, "[]\n") == 0) {
        printf("[0]\n");
        return 0;
    }
    
    char* ptr = line + 1; // Skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            int a = 0, b = 0;
            while (*ptr >= '0' && *ptr <= '9') {
                a = a * 10 + (*ptr - '0');
                ptr++;
            }
            if (*ptr == ',') ptr++;
            while (*ptr >= '0' && *ptr <= '9') {
                b = b * 10 + (*ptr - '0');
                ptr++;
            }
            edges[edgesSize][0] = a;
            edges[edgesSize][1] = b;
            edgesSize++;
            while (*ptr && *ptr != '[' && *ptr != ']') ptr++;
        } else {
            ptr++;
        }
    }
    
    int* edgesPtrs[MAX_N];
    for (int i = 0; i < edgesSize; i++) {
        edgesPtrs[i] = edges[i];
    }
    
    int returnSize;
    int* result = solution(edgesPtrs, edgesSize, NULL, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n starting nodes, we run BFS which visits all n nodes

⚠ Quadratic Growth

Space Complexity

O(n)

Queue for BFS and visited array for each simulation

⚡ Linearithmic Space

8.4K Views

Medium Frequency

~35 min Avg. Time

256 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

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler