Is Maximum Manhattan Distance After All Moves easy or hard?

The problem is typically classified as Medium because the brute-force idea is obvious but inefficient. The challenge lies in recognizing the Manhattan distance transformation and applying a greedy optimization to reach the O(n) solution.

Maximum Manhattan Distance After All Moves Python/Java solution

Implement the greedy quadrant evaluation by scanning the move string and calculating contributions for each direction relative to the target orientation. Repeat the computation four times for all sign combinations. The algorithm works the same in Python, Java, or C++ and runs in O(n) time with constant space.

How to solve Maximum Manhattan Distance After All Moves in O(n)?

Compute the contribution of each move relative to a target quadrant. Treat aligned moves as +1 and opposite moves as -1, then sum the sequence. If modifications are allowed, convert the worst moves first since each flip improves the score by 2. Repeat for all four quadrant combinations and return the maximum.

What is the best approach for Maximum Manhattan Distance After All Moves?

The most efficient method evaluates all four possible Manhattan distance sign combinations and greedily flips moves that reduce the score. By transforming |x| + |y| into max(sx*x + sy*y), the problem becomes choosing directions that contribute positively. This approach runs in O(n) time and O(1) space.

Is Maximum Manhattan Distance After All Moves asked at Google/Amazon/Meta?

Grid movement and Manhattan distance optimization problems frequently appear in interviews at companies like Amazon, Google, and Meta. The exact problem may vary, but the underlying ideas—coordinate transforms, greedy optimization, and directional counting—are common interview patterns.

What data structure is used in Maximum Manhattan Distance After All Moves?

The solution mainly relies on simple counters and arithmetic rather than complex data structures. Direction counts or running sums track how moves affect the x and y coordinates. This keeps both time and space complexity minimal.

What is the time complexity of Maximum Manhattan Distance After All Moves?

The optimal solution runs in O(n) time because it scans the move sequence a constant number of times while evaluating four possible quadrant orientations. Only counters and simple arithmetic are used, so the space complexity remains O(1).

Description Hints 3 Solution Video 8:37

3968. Maximum Manhattan Distance After All Moves

Medium63.3% acceptance

You are given a string moves consisting of the characters 'U', 'D', 'L', 'R', and '_'.

Starting from the origin (0, 0), each character represents one move on a 2D plane:

'U': Move up by 1 unit.
'D': Move down by 1 unit.
'L': Move left by 1 unit.
'R': Move right by 1 unit.
'_': Can be independently replaced with any one of 'U', 'D', 'L', or 'R'.

Return the maximum Manhattan distance from the origin that can be achieved after all moves have been performed.

Example 1:

Input: moves = "L_D_"

Output: 4

Explanation:

One optimal choice is:

'L': (0, 0) -> (-1, 0)
'_' treated as 'D': (-1, 0) -> (-1, -1)
'D': (-1, -1) -> (-1, -2)
'_' treated as 'L': (-1, -2) -> (-2, -2)

The final Manhattan distance from the origin is |0 - (-2)| + |0 - (-2)| = 4.

Example 2:

Input: moves = "U_R"

Output: 3

Explanation:

One optimal choice is:

'U': (0, 0) -> (0, 1)
'_' treated as 'U': (0, 1) -> (0, 2)
'R': (0, 2) -> (1, 2)

The final Manhattan distance from the origin is |0 - 1| + |0 - 2| = 3.

Constraints:

1 <= moves.length <= 10⁵
moves consists of only 'U', 'D', 'L', 'R', and '_'.

Topics

Hints open one at a time

Hint 1

Count the net horizontal movement, net vertical movement, and the number of underscores.

Hint 2

Without underscores, the final distance is abs(x) + abs(y).

Hint 3

Each underscore can always be chosen to increase the final Manhattan distance by 1, so add the number of underscores to the fixed-move distance.

8:37

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

3968. Maximum Manhattan Distance After All Moves

Topics

Hints open one at a time

Similar problems