**Race To The End (RTTE)**

**Tags: Complete Search, Shortest path in DAG.**

**Problem:**

practice

**Author: Naman.
Tester: Shami.**

There are two possible approaches for this problem.

**Brute force**

Since the limit on N is very small, we can try all possible combinations and find the result. We can store the minimum steps to reach each index in an array (arr).

**Steps:**

- Start from index 0. a[0] = 0
- For each index ‘i’, we update value of a[i] = min(a[i], a[i+1]+1)

we don’t need to check a[i-1] as it would already have been processed because we started from left. - Find all indices j to the right such that a[j] == a[i]

a. For each j, update all left indices similar to step #2. - Answer is stored in a[N-1].

**Graph**

Let’s consider each index ‘i’ as a node and all possible moves as directed edges. So the edges from A[i] will be

- A[i-1]
- A[i+1]
- All A[j] such that A[j] == A[i]

Complexity to generate graph: O(N^2)

Notice that the directed graph may have back edges, but it does not matter in our case. Now we can apply BFS starting from index 0 and count the minimum number of levels to reach N. The number of levels is the answer.