# I want reduce the time complexity for this ladder problem to find the minimum ladders required

I was trying to attempt below given challenge. I tried multiple ways to solve the problem but none of them were good enough to pass the time limit. Please advise if you have any idea to improve on this.

Problem: You are visiting a building of N floors. On every floor, only one ladder of specified length is present. If the length of the ladder is x units, you can reach y floors above from the current one.

You can leave the ladder in between in order to change the ladder, but you can only start from the starting floor of the ladder.

You are given Q questions. In each question, you will be given a floor number. For each question, you have to tell the least number of ladders required to reach given floor. Initially, you are on the ground floor.

Input Format: The first line contains an integer T, indicating the number of test cases. For each test case: The first line contains an integer N, indicating number of floors in the building. Next line contains N space separated positive integers which denote the length of ladder at each floor (First integer corresponds to ladder length on ground floor, second integer corresponds to ladder length on first floor and so on) . Next line contains an integer Q, indicating number of questions. Following Q lines contain an integer each, denoting the floor number for which answer is to be computed.

Output Format: For each question, print the least number of ladders required required to reach given floor. Answer for each question should come in a new line.

Sample Input:

1
10
2 2 1 1 2 2 3 1 1 1
10
5
4
3
2
1
10
9
8
7
6


Sample Output:

4
3
2
1
1
6
5
5
5
4


Problem Reference

Solution:

class Program
{
static void Main(string[] args)
{
StringBuilder sb = new StringBuilder("");
for (int i = 0; i < T; i++)
{
sb.EnsureCapacity(sb.Length + (5 * N));
int[] numOfStairs = new int[N + 1];
numOfStairs[0] = 0;
int[] reaches = new int[N];
for (int j = 0; j < stairs.Length; j++)
{
int length = Convert.ToInt32(stairs[j]);
reaches[j] = j + length;
}

for (int j = 0; j < Q; j++)
{
sb.AppendLine(GetShortestPath(target, reaches.Take(target).ToArray(), numOfStairs).ToString());
}
}
Console.WriteLine(sb.ToString());
}
static int GetShortestPath(int target, int[] reaches, int[] numOfStairs)
{
if (numOfStairs[target] == 0 && target != 0)
{
List<int> connectedFloors = GetPreviousFloorList(target, reaches);
int[] shortestPaths = new int[connectedFloors.Count];
for (int i = 0; i < connectedFloors.Count; i++)
{
int shortestPath = GetShortestPath(connectedFloors[i], reaches.Take(connectedFloors[i]).ToArray(), numOfStairs);
shortestPaths[i] = shortestPath;
}
int result = shortestPaths.Min() + 1;
numOfStairs[target] = result;
return result;
}
else
{
return numOfStairs[target];
}
}
static List<int> GetPreviousFloorList(int target, int[] reaches)
{
List<int> floors = new List<int>(target / 2);
for (int i = 0; i < target; i++)
{
if (reaches[i] >= target)
}
return floors;
}
}

• The current question title, which states your concerns about the code, applies to too many questions on this site to be useful. The site standard is for the title to simply state the task accomplished by the code. Please see How do I ask a good question?. Commented May 4, 2021 at 8:22
• Commented May 4, 2021 at 8:22
• Thanks for the advice, I will do that and update the question accordingly. Commented May 5, 2021 at 8:17

Applied few minor optimisations to the code from the OP's answer. Also fixed naming issues (locals name starts from a lower-cased letter).

class Program
{
static void Main(string[] args)
{
StringBuilder sb = new StringBuilder();
for (int i = 0; i < t; i++)
{
int[] numOfStairs = new int[n + 1];
int floorsMarked = 0;
for (int j = 0; j < str.Length; j++)
{
int length = int.Parse(str[j]);
int reach = j + length > n ? n : j + length;
while (floorsMarked < reach)
{
floorsMarked++;
numOfStairs[floorsMarked] = numOfStairs[j] + 1;
}
if (reach == n)
break;
}
for (int j = 0; j < q; j++)
{
sb.Append(numOfStairs[target]).AppendLine();
}
}
Console.Write(sb);
}
}

• Thanks for the input. I noticed that you changed Convert.Int32 to int.parse which is a tad bit faster but i do not see any other changes that would reduce execution time. Let me know if i am missing anything. I also noticed that you reduced the size of Array "numOfStairs" to n from n+1. I think that would cause a IndexOutOfBound since for the last floor, the index would be n -> size needs to be n+1. Commented May 4, 2021 at 5:04
• @AkshayGupta Console.Write(sb); didn't affect the performance? Further performance tweaks require .NET Core, and more details on input steucture sizes. For example, you may use ArrayPool<T> instead of allocating array. Span<T> can be also useful with stack allocations. Commented May 4, 2021 at 6:01
• Thanks for the inputs. i will look into implementing your advice. Also, i did not know that Console.Write(sb); is faster than Console.WriteLine(sb); Commented May 5, 2021 at 8:57
• @Akshay i don't know is it faster but i know that WriteLine and Wtite accepts StringBuilder as it is. Probably it avoids allocating the output string. Write differs from WriteLine only at ending LF. I changed to Write because you already have ending LF in sb, written there with AppendLine. Commented May 12, 2021 at 18:11

I was finally able to reduce it enough to return result for 1 million inputs in around 10 secs.

class Program
{
static void Main(string[] args)
{
StringBuilder sb = new StringBuilder("");
for (int i = 0; i < T; i++)
{
int[] numOfStairs = new int[N + 1];
numOfStairs[0] = 0;
int floorsMarked = 0;
for (int j = 0; j < str.Length; j++)
{
int length = Convert.ToInt32(str[j]);
int reach = j + length > N ? N : j + length;
while (floorsMarked < reach)
{
floorsMarked++;
numOfStairs[floorsMarked] = numOfStairs[j] + 1;
}
if (reach >= N)
break;
}