We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
That's a fine variation. Note though that BFS is also O(n). |E| <= 6*100 if you construct the adjacency matrix so that a ladder/snake from i to j means all squares a die roll from i are adjacent to j and not adjacent to i. This means in effect any additional edge created by a snake or ladder is balanced out by the deletion of a die roll adjacency.
BFS has time complexity O(|V| + |E|), and so if we alter the problem slightly so that |V| = |N| can be an arbitrary number and the number of ladders/snakes is linear in n then O(|V| + |E|) = O(N + O(N)) = O(N).
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Snakes and Ladders: The Quickest Way Up
You are viewing a single comment's thread. Return to all comments →
That's a fine variation. Note though that BFS is also O(n). |E| <= 6*100 if you construct the adjacency matrix so that a ladder/snake from i to j means all squares a die roll from i are adjacent to j and not adjacent to i. This means in effect any additional edge created by a snake or ladder is balanced out by the deletion of a die roll adjacency.
BFS has time complexity O(|V| + |E|), and so if we alter the problem slightly so that |V| = |N| can be an arbitrary number and the number of ladders/snakes is linear in n then O(|V| + |E|) = O(N + O(N)) = O(N).