Golden Brick Road

Problem

Julia has reached the Munchkin kingdom in the magical land of Oz. To enter the castle of the great wizard, she needs to cross the Golden Brick Road, where all the bricks are aligned in a straight line.

To cross this road, there are some conditions set by the wizard:

• There are N bricks, and each brick is labeled randomly with a number from 0-9.
• Julia is initially on the 1st brick and needs to reach the Nth brick to cross the Golden Brick Road.
• If she is on the ith brick with value V, then she can move to:
  • The (i+1)th brick (one step forward)
  • The (i-1)th brick (one step backward)
  • Any brick with the same value V (teleport)

Your task is to help Julia find the minimum number of moves required to reach the Nth brick.

This is a classic BFS problem where you need to find the shortest path in an implicit graph.

Constraints

• Number of bricks N: 1 ≤ N ≤ 10^5
• Each brick value is between 0 and 9
• Julia starts at brick 1 (index 0) and needs to reach brick N (index N-1)
• The answer is always reachable (at least by walking step by step)

Examples

Example 1

Input:

N = 6
A = [5, 2, 3, 4, 5, 3]

Output:

2

Explanation: Julia needs to reach the 6th brick to cross the Golden Brick Road. She can do so optimally:

1. She is at the 1st brick of value 5, so she can go to the 5th brick, as both bricks have the same value 5.
2. Now, she can move to the 6th brick by moving one step forward (moving to the (i+1)th brick). Since Julia took 2 moves to cross the Golden Brick Road, 2 is returned as the output.

Example 2

Input:

N = 5
A = [1, 2, 3, 4, 1]

Output:

1

Explanation: Julia needs to reach the 5th brick. She can do so optimally:

1. She is at the 1st brick of value 1, so she can go to the 5th brick, as both bricks hold the same value 1. Since Julia took 1 move to cross the Golden Brick Road, 1 is returned as the output.

Example 3

Input:

N = 4
A = [1, 2, 3, 4]

Output:

3

Explanation: No teleportation possible (all values unique). Julia must walk step by step: 1→2→3→4, taking 3 moves.

Function Signature

# Read only region start
class UserMainCode(object):
    @classmethod
    def leastMoves(cls, input1, input2):
        '''
        input1 : int
        input2 : int[]

        Expected return type : int
        '''
        # Read only region end
        # Write code here
        pass

Estimated Time

30-40 minutes

Tags

bfs graph shortest-path interview medium real-interview