algoadvance

You are given a string moves of length n representing the moves of an object in the coordinate plane. The object starts at the origin (0, 0), and each character in the string represents a move:

• ‘L’ signifies a move one unit left (decreasing the x-coordinate)
• ‘R’ signifies a move one unit right (increasing the x-coordinate)
• ‘U’ signifies a move one unit up (increasing the y-coordinate)
• ‘D’ signifies a move one unit down (decreasing the y-coordinate)

You need to determine the Manhattan distance of the object’s furthest point from the origin after performing all the moves.

The Manhattan distance between two points (x1, y1) and (x2, y2) is |x1 - x2| + |y1 - y2|.

Clarifying Questions

1. Will the string moves always be non-empty?
   • For the purpose of this problem, let’s assume that the input will always be non-null and non-empty.
2. Do the moves only consist of ‘L’, ‘R’, ‘U’, and ‘D’?
   • Yes, we assume the string only contains valid move characters as specified.
3. Are there any constraints on the length of the string moves?
   • We’ll assume the given length of the string moves is within a reasonable limit for computation in a coding interview setting.

Strategy

1. Initialize Starting Position:
   • Initialize x and y to 0 representing the starting coordinates.
2. Iterate Through Moves:
   • For each move in the string, update the coordinates (x, y) accordingly:
     • ‘L’ decreases the x-coordinate.
     • ‘R’ increases the x-coordinate.
     • ‘U’ increases the y-coordinate.
     • ‘D’ decreases the y-coordinate.
3. Calculate Manhattan Distance:
   • After processing all moves, calculate the Manhattan distance from the origin using the formula |x| + |y|.

Code

def furthest_point_from_origin(moves: str) -> int:
    x, y = 0, 0
    
    for move in moves:
        if move == 'L':
            x -= 1
        elif move == 'R':
            x += 1
        elif move == 'U':
            y += 1
        elif move == 'D':
            y -= 1
    
    return abs(x) + abs(y)

# Example usage:
moves = "LURDURD"
print(furthest_point_from_origin(moves))  # Output calculation based on the moves

Time Complexity

• Time Complexity: O(n), where n is the length of the string moves. This is because we iterate through each character in the string once.
• Space Complexity: O(1), because we only use a fixed amount of additional space to store the coordinates x and y.

Feel free to test this function with different inputs to verify its correctness!

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?