Bulb Switcher III

There are n bulbs arranged in a line, numbered from 1 to n from left to right. Initially, all bulb are turned off.

At time k (where k ranges from 0 to n-1), we turn on the bulb at position light[k].

A bulb turns blue when both conditions are met:

• The bulb is currently on
• All bulbs to its left are also on

Return the number of moments when all turned-on bulbs are blue.

Example 1

Input: light = [2,1,3,5,4] Output: 3 Explanation: All turned-on bulbs are blue at moments 1, 2, and 4.

Example 2

Input: light = [3,2,4,1,5] Output: 2

Example 3

Input: light = [4,1,2,3] Output: 1

Solution

var numTimesAllBlue = function(light) {
    let maxIndex = 1;
    let result = 0;
    
    for (let i = 0; i < light.length; i++) {
        maxIndex = Math.max(light[i], maxIndex);
        if (maxIndex === i + 1) {
            result++;
        }
    }
    return result;
};

The key insight is that all bulbs are blue when the maximum turned-on bulb number equals the total count of turned-on bulbs.

Time Needed to Inform All Employees

There are n employees in a company, each with a unique ID from 0 to n-1. The head of the company is identified by headID.

Each employee has a direct manager specified in the manager array, where manager[i] is the direct manager of employee i. For the head, manager[headID] = -1. The relationship forms a tree structure.

The head wants to inform all employees about an urgent message. They will first notify their direct subordinates, who then notify their subordinates, continuing until all employees receive the message.

Employee i needs informTime[i] minutes to inform all their direct subordinates. Return the total minutes needed to inform all employees.

Example 1

Input: n = 1, headID = 0, manager = [-1], informTime = [0] Output: 0

Example 2

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0] Output: 1

Example 3

Input: n = 7, headID = 6, manager = [1,2,3,4,5,6,-1], informTime = [0,6,5,4,3,2,1] Output: 21

Solution

var numOfMinutes = function(n, headID, manager, informTime) {
    const buildTree = (manager) => {
        const children = new Array(manager.length).fill(null).map(() => []);
        for (let i = 0; i < manager.length; i++) {
            if (manager[i] !== -1) {
                children[manager[i]].push(i);
            }
        }
        return children;
    };
    
    const findMaxTime = (children, informTime, employeeId, currentTime) => {
        currentTime += informTime[employeeId];
        
        if (!children[employeeId].length) {
            return currentTime;
        }
        
        let maxChildTime = 0;
        for (const subordinate of children[employeeId]) {
            maxChildTime = Math.max(
                maxChildTime,
                findMaxTime(children, informTime, subordinate, currentTime)
            );
        }
        return maxChildTime;
    };
    
    const children = buildTree(manager);
    return findMaxTime(children, informTime, headID, 0);
};

This problem requires finding the longest path from the head to any leaf in the tree, which represents the maximum time needed to inform all employees.

Frog Position After T Seconds

Given an undirected tree with n vertices numbered from 1 to n. A frog starts at vertex 1. The rules are:

• In one second, the frog jumps from its current vertex to an unvisited adjacent vertex
• The frog cannot return to visited vertices
• If multiple unvisited vertices are available, the frog chooses uniformly at random
• If no unvisited vertices are available, the frog stays at its current posiiton

Givan the edges array describing the tree edges, return the probability that the frog is at the target vertex after t seconds.

Example 1

Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4 Output: 0.16666666666666666

Example 2

Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7 Output: 0.3333333333333333

Example 3

Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 20, target = 6 Output: 0.16666666666666666

Solution

var frogPosition = function(n, edges, t, target) {
    const adjacencyList = new Array(n + 1).fill(null).map(() => []);
    
    for (const [u, v] of edges) {
        adjacencyList[u].push(v);
        adjacencyList[v].push(u);
    }
    
    const queue = [];
    queue.push({ vertex: 1, probability: 1.0, time: 0 });
    
    const visited = new Array(n + 1).fill(false);
    visited[1] = true;
    
    while (queue.length > 0) {
        const { vertex, probability, time } = queue.shift();
        
        if (vertex === target && time === t) {
            return probability;
        }
        
        let availableMoves = 0;
        for (const neighbor of adjacencyList[vertex]) {
            if (!visited[neighbor]) {
                availableMoves++;
            }
        }
        
        if (time < t) {
            let hasUnvisitedNeighbor = false;
            
            for (const neighbor of adjacencyList[vertex]) {
                if (!visited[neighbor]) {
                    hasUnvisitedNeighbor = true;
                    visited[neighbor] = true;
                    queue.push({
                        vertex: neighbor,
                        probability: probability / availableMoves,
                        time: time + 1
                    });
                }
            }
            
            if (!hasUnvisitedNeighbor) {
                queue.push({
                    vertex: vertex,
                    probability: probability,
                    time: time + 1
                });
            }
        }
    }
    
    return 0.0;
};

This solution uses BFS to simulate all possible frog movements, calculating probabilities at each step. When the frog reaches a leaf node before time t expires, it stays at that position for remaining time steps.