Problem

A city is represented as a bi-directional connected graph with n vertices where each vertex is labeled from 1 to n (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself. The time taken to traverse any edge is time minutes.

Each vertex has a traffic signal which changes its color from green to red and vice versa every change minutes. All signals change at the same time. You can enter a vertex at any time, but can leave a vertex only when the signal is green. You cannot wait at a vertex if the signal is green.

The second minimum value is defined as the smallest value strictly larger than the minimum value.

  • For example the second minimum value of [2, 3, 4] is 3, and the second minimum value of [2, 2, 4] is 4.

Given n, edges, time, and change, return the second minimum time it will take to go from vertex 1 to vertex n.

Notes:

  • You can go through any vertex any number of times, including 1 and n.
  • You can assume that when the journey starts, all signals have just turned green.

Examples

Example 1:

graph TD
	1 --- 2
	1 --- 3
	1 --- 4
	3 --- 4
	4 --- 5
  
graph TD
	1 --- 2
	1 -->|1| 3
	1 -->|1| 4
	3 -->|2| 4
	4 -->|2| 5
	4 -->|3| 5

linkStyle 2 stroke:blue, stroke-width:4px;
linkStyle 4 stroke:blue, stroke-width:4px;

linkStyle 1 stroke:gold, stroke-width:4px;
linkStyle 3 stroke:gold, stroke-width:4px;
linkStyle 5 stroke:gold, stroke-width:4px;
  
Input: n = 5, edges = [ [1,2],[1,3],[1,4],[3,4],[4,5] ], time = 3, change = 5
Output: 13
Explanation:
The figure above shows the given graph.
The blue path in the below figure is the minimum time path.
The time taken is:
- Start at 1, time elapsed=0
- 1 -> 4: 3 minutes, time elapsed=3
- 4 -> 5: 3 minutes, time elapsed=6
Hence the minimum time needed is 6 minutes.

The golden path shows the path to get the second minimum time.
- Start at 1, time elapsed=0
- 1 -> 3: 3 minutes, time elapsed=3
- 3 -> 4: 3 minutes, time elapsed=6
- Wait at 4 for 4 minutes, time elapsed=10
- 4 -> 5: 3 minutes, time elapsed=13
Hence the second minimum time is 13 minutes.

Example 2:

graph LR;
	1 --- 2
  
Input: n = 2, edges = [ [1,2] ], time = 3, change = 2
Output: 11
Explanation:
The minimum time path is 1 -> 2 with time = 3 minutes.
The second minimum time path is 1 -> 2 -> 1 -> 2 with time = 11 minutes.

Solution

To find the second minimum time required to travel from vertex 1 to vertex n in a graph with traffic signals, we need to account for both path traversal and the waiting times caused by the traffic signals’ cycle. The key insights are:

  • Each edge traversal takes exactly time minutes.
  • Each signal alternates every change minutes between green and red.
  • You can only leave a vertex when the signal is green.

Method 1 - Dijkstra Algorithm

We can solve this problem using a modified Dijkstra’s or shortest path algorithm. This will help us account for the different paths’ travel times and keep track of the second minimum time.

Here are the steps we can take:

  1. Build the graph as adjacency list to representation.
  2. Setup the dijkstra algorithm
    • We use Priority Queue to store states represented as (current_time, current_vertex), and it is a min heap based on time.
    • Add node 1 with time 0
    • Time tracking: We use distance[n + 1][2] matrix to not just minimum time to reach each neighboring vertex, but also the second minimum time as well. For dist[1][0] minimum time will be 0. We use distance[n + 1] as nodes start with 1, not 0.
  3. Start Dijkstra Algorithm
    • Poll out the node from priority queue based on time
    • Check if it’s a red light when we are at current node, if it is, calculate the waiting time until the next green light. Our currentTime increases because of that
    • Now, we start processing all the neighbours and update the minimum and second minimum times to reach each neighboring vertex.
      • If currentTime is less than distance[v][0], set distance[v][1] as distance[v][0] and distance[v][0] as currentTime
      • If currentTime is less than distance[v][1], set distance[v][1] as currentTime
  4. Return the result as distance[n][1]

Code

Java
class Solution {

	public int secondMinimum(int n, int[][] edges, int time, int change) {
		// Initialize the graph
		List < List<Integer>> graph = new ArrayList<>();

		for (int i = 0; i < n + 1; i++) {
			graph.add(new ArrayList<>());
		}

		for (int[] edge: edges) {
			int u = edge[0];
			int v = edge[1];
			graph.get(u).add(v);
			graph.get(v).add(u);
		}

		// Priority queue to store (time, vertex)
		PriorityQueue < int[] > pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
		pq.offer(new int[] {
			0, 1
		});

		// Array to store min and second min time to reach each node
		int[][] dist = new int[n + 1][2];

		for (int i = 0; i <= n; i++) {
			Arrays.fill(dist[i], Integer.MAX_VALUE);
		}

		dist[1][0] = 0;

		while (!pq.isEmpty()) {
			int[] current = pq.poll();
			int currentTime = current[0];
			int u = current[1];

			for (int v: graph.get(u)) {
				int nextTime = currentTime;

				// Compute the time considering traffic signal
				if ((nextTime / change) % 2 == 1) { // If it's red light
					nextTime = (nextTime / change + 1) * change;
				}

				nextTime += time;

				if (nextTime < dist[v][0]) {
					dist[v][1] = dist[v][0];
					dist[v][0] = nextTime;
					pq.offer(new int[] {
						nextTime, v
					});
				} else if (nextTime > dist[v][0] && nextTime  <  dist[v][1]) {
					dist[v][1] = nextTime;
					pq.offer(new int[] {
						nextTime, v
					});
				}
			}
		}

		return dist[n][1];
	}

}

Complexity

  • ⏰ Time complexity: O(E log V), where E is number of edges and V is number of vertices
    • Building the graph: (O(E))
    • Priority queue operations: (O(E \log V))
    • Dijkstra’s algorithm-like edge relaxations: (O(E \log V))
  • 🧺 Space complexity: O(V + E)
    • Graph representation: (O(V + E))
    • Distance arrays: (O(V))
    • Priority queue operations: (O(E))