Server Information Propagation

Moderate

0/80

0 upvote

Asked in company

Problem statement

You are given n servers, indexed from 0 to n-1. Each server i has a specific sendTime[i], which dictates how it can transmit information. In a single step, a server at index i can send information to:

The server at index i + sendTime[i], if this index is within the bounds [0, n-1].

The server at index i - sendTime[i], if this index is within the bounds [0, n-1].

Initially, only the last server (at index n-1) possesses a piece of information. This information then spreads through the network in steps.

Your task is to determine the minimum number of steps required for each server to receive the information. If a server is unreachable from the starting server, its minimum number of steps is considered -1.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer N, the number of servers.

The second line contains N space-separated integers, representing the sendTime array.

Output Format:

Print a single line containing N space-separated integers, where the i-th integer is the minimum number of steps for server i to receive the information.

Note:

This problem can be modeled as finding the shortest path from a single source (n-1) to all other nodes in an unweighted graph. Breadth-First Search (BFS) is the ideal algorithm for this task.

Sample Input 1:

5
1 1 1 1 1

Sample Output 1:

4 3 2 1 0

Explanation for Sample 1:

The information starts at server 4 (0 steps).
In 1 step, server 4 sends to 4-1=3.
In 2 steps, server 3 sends to 3-1=2.
In 3 steps, server 2 sends to 2-1=1.
In 4 steps, server 1 sends to 1-1=0.
The minimum steps for each server are [4, 3, 2, 1, 0].

Sample Input 2:

6
2 2 2 2 2 2

Sample Output 2:

-1 2 -1 1 -1 0

Explanation for Sample 2:

The information starts at server 5 (0 steps).
Server 5 sends to 5-2=3 (1 step).
Server 3 sends to 3-2=1 (2 steps).
The path ends. Servers 0, 2, and 4 are never reached, so their step counts are -1.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

1 <= N <= 10^5
1 <= sendTime[i] <= N

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Server Information Propagation

Console