Furthest Point From Origin Interview Question for Amazon

You are given a string moves of length n consisting only of characters 'L', 'R', and '_'. The string represents your movement on a number line starting from the origin 0.

In the i<sup>th</sup> move, you can choose one of the following directions:

move to the left if moves[i] = 'L' or moves[i] = '_'
move to the right if moves[i] = 'R' or moves[i] = '_'

Return the distance from the origin of the furthest point you can get to after n moves.

Example 1:

Input: moves = "L_RL__R"
Output: 3
Explanation: The furthest point we can reach from the origin 0 is point -3 through the following sequence of moves "LLRLLLR".

Example 2:

Input: moves = "_R__LL_"
Output: 5
Explanation: The furthest point we can reach from the origin 0 is point -5 through the following sequence of moves "LRLLLLL".

Example 3:

Input: moves = "_______"
Output: 7
Explanation: The furthest point we can reach from the origin 0 is point 7 through the following sequence of moves "RRRRRRR".

What is the most efficient way to calculate this distance, and what is the time and space complexity of your solution?

Let's analyze the problem. We are given a string of moves, and we can move left or right. The goal is to find the furthest distance from the origin we can reach. When we encounter a '_', we have a choice to go left or right. We want to maximize the absolute value of our final position. A naive solution is to try all possible combinations of moves when we encounter a '_'. This would involve recursion or backtracking.

Naive Solution (Brute Force)

We can explore all possible move sequences using recursion. At each underscore, we branch into two possibilities: moving left or moving right. We keep track of the current position and update the maximum distance from the origin found so far.

def furthest_distance_brute_force(moves):
    def solve(index, current_position):
        nonlocal max_distance
        if index == len(moves):
            max_distance = max(max_distance, abs(current_position))
            return

        if moves[index] == 'L':
            solve(index + 1, current_position - 1)
        elif moves[index] == 'R':
            solve(index + 1, current_position + 1)
        else:
            solve(index + 1, current_position - 1)
            solve(index + 1, current_position + 1)

    max_distance = 0
    solve(0, 0)
    return max_distance

Big O analysis

Time Complexity: O(2^k), where k is the number of underscores in the input string. In the worst case, where all characters are underscores, we have 2 options for each move leading to exponential time complexity.
Space Complexity: O(k), due to the call stack of the recursive calls. This can be at most the number of underscores. In the worst case this would be O(n).

Optimal Solution (Greedy)

A more efficient approach is to consider the leftmost and rightmost possible positions. We calculate the maximum possible rightward distance and the maximum possible leftward distance. The underscores are converted to moves in the direction that maximizes these distances.

Count the number of R moves and underscores. Let this be right_moves.
Count the number of L moves. Let this be left_moves.
The maximum rightward distance is right_moves. This is achieved by treating every underscore as a right move.
The maximum leftward distance (in absolute value) is left_moves + number of underscores. But this approach is wrong because each underscore can be either R or L, we want to find the furthest distance from the origin.
The optimal approach is simply to count all 'R' and all '_' as moving right, and all 'L' as moving left. Then, the furthest distance is the absolute value of this net movement.

def furthest_distance(moves):
    right_moves = 0
    left_moves = 0

    for move in moves:
        if move == 'R' or move == '_':
            right_moves += 1
        elif move == 'L':
            left_moves += 1

    return right_moves - left_moves

Big O analysis

Time Complexity: O(n), where n is the length of the input string. We iterate through the string once.
Space Complexity: O(1). We use a constant amount of extra space.

Edge Cases:

Empty string: The problem statement constraints specify that the string will always have at least one character, so we don't need to check for an empty string.
String with only underscores: The algorithm works correctly in this case.
String with only 'L' or 'R' moves: The algorithm works correctly in this case as well.