Maximum Manhattan Distance After All Moves solution and explanation
7 more videos on this problem
Maximum Manhattan Distance After All Moves | LeetCode 3968 | Weekly Contest 507 | Developer CoderDeveloper Coder · 8:37 · 205 views
3968. Maximum Manhattan Distance After All Moves (Leetcode Medium)Programming Live with Larry · 4:27 · 129 views
LeetCode Weekly Contest — Maximum Manhattan Distance After All Moves (Q1) | Easy Trick Explained!Gopo workspace · 7:01 · 103 views
LeetCode 3968 | Maximum Manhattan Distance After All Moves | Java | HindiCode Kage · 7:28 · 61 views
Maximum Manhattan Distance After All MovesI | Leetcod 3968 | Explanation With Code | javacodewithsitaram · 17:00 · 30 views
LeetCode 3968: Maximum Manhattan Distance After All Moves | C++ SolutionAeXel · 8:23 · 25 views
Weekly Contest 507 | Leetcode 3968 | Maximum Manhattan Distance After All MovesCode Like Him · 3:29 · 21 views
Maximum Manhattan Distance After All Moves | Leetcode weekly contest 507 | #3968UMANG AGRAWAL · 11:17 · 1 view
The problem
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 <= 105movesconsists of only'U','D','L','R', and'_'.
Approach overview
Problem Overview: You are given a sequence of moves on a 2D grid using directions like N, S, E, and W. After performing all moves, the goal is to maximize the final Manhattan distance from the origin. Some moves can be modified, so the challenge is choosing changes that push the final position as far from (0,0) as possible.
Approach 1: Brute Force Direction Replacement (Exponential)
The most direct idea is to try all possible ways to modify the allowed moves. For every changeable move, replace it with each of the four directions and simulate the final position. After executing the entire sequence, compute the Manhattan distance |x| + |y|. This approach explores a large search space because each modification multiplies the number of possibilities. Time complexity grows exponentially (roughly O(4^k * n)), and space complexity is O(1) excluding recursion. This method only works for extremely small inputs and mainly helps build intuition about how direction choices affect the final coordinates.
Approach 2: Count Directions and Greedy Adjustments (O(n))
A more practical observation: the final Manhattan distance depends only on the net horizontal and vertical displacement. Moves E and W affect the x-axis, while N and S affect the y-axis. By counting each direction, you can compute the base displacement x = E - W and y = N - S. If modifications are allowed, changing a move that opposes your target direction increases distance the most (often by 2 units because it flips direction). A greedy strategy converts the most harmful moves first. Iterating through the string once to collect counts gives O(n) time and O(1) space.
Approach 3: Quadrant Maximization Trick (Optimal O(n))
The Manhattan distance can be rewritten as |x| + |y| = max(sx * x + sy * y) where sx and sy are either +1 or -1. That means the optimal result must correspond to one of four quadrants. For each quadrant, treat moves aligned with that direction as +1 and opposite moves as -1. Iterate through the sequence and compute the base score. If changes are allowed, flipping an unfavorable move increases the score by 2. Apply modifications to the worst contributors until you run out of changes. Evaluate all four quadrant configurations and take the maximum. This runs in O(4n) time (effectively O(n)) with O(1) extra space.
Conceptually this solution relies on understanding greedy algorithms and how Manhattan distance behaves under sign transformations. Many candidates also derive it by modeling the path as coordinate deltas and evaluating directional bias, a common trick in grid mathematics and simulation problems.
Recommended for interviews: The quadrant maximization approach. Interviewers expect you to recognize that Manhattan distance can be transformed into four linear expressions and optimized greedily. Mentioning the brute-force idea shows you understand the search space, but deriving the O(n) greedy solution demonstrates strong problem-solving skills.
Solution
We can use a variable x to record the vertical distance, a variable y to record the horizontal distance, and a variable z to record the number of replaceable moves.
Then the final Manhattan distance is |x| + |y| + z.
The time complexity is O(n), where n is the length of the string moves. The space complexity is O(1).
class Solution:
def maxDistance(self, moves: str) -> int:
x = y = z = 0
for c in moves:
if c == "U":
x -= 1
elif c == "D":
x += 1
elif c == "L":
y -= 1
elif c == "R":
y += 1
else:
z += 1
return abs(x) + abs(y) + zclass Solution {
public int maxDistance(String moves) {
int x = 0, y = 0, z = 0;
for (char c : moves.toCharArray()) {
if (c == 'U') {
x -= 1;
} else if (c == 'D') {
x += 1;
} else if (c == 'L') {
y -= 1;
} else if (c == 'R') {
y += 1;
} else {
z += 1;
}
}
return Math.abs(x) + Math.abs(y) + z;
}
}class Solution {
public:
int maxDistance(string moves) {
int x = 0, y = 0, z = 0;
for (char c : moves) {
if (c == 'U') {
x -= 1;
} else if (c == 'D') {
x += 1;
} else if (c == 'L') {
y -= 1;
} else if (c == 'R') {
y += 1;
} else {
z += 1;
}
}
return abs(x) + abs(y) + z;
}
};function maxDistance(moves: string): number {
let [x, y, z] = [0, 0, 0];
for (const c of moves) {
if (c === 'U') {
x -= 1;
} else if (c === 'D') {
x += 1;
} else if (c === 'L') {
y -= 1;
} else if (c === 'R') {
y += 1;
} else {
z += 1;
}
}
return Math.abs(x) + Math.abs(y) + z;
}func maxDistance(moves string) int {
x, y, z := 0, 0, 0
for _, c := range moves {
if c == 'U' {
x -= 1
} else if c == 'D' {
x += 1
} else if c == 'L' {
y -= 1
} else if c == 'R' {
y += 1
} else {
z += 1
}
}
return abs(x) + abs(y) + z
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Direction Replacement | O(4^k * n) | O(1) | Only useful for understanding the search space or extremely small inputs |
| Direction Counting + Greedy Changes | O(n) | O(1) | When modifications are limited and direction counts determine displacement |
| Quadrant Maximization (Optimal) | O(n) | O(1) | Best general solution; evaluates all Manhattan sign combinations efficiently |
Frequently asked questions
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).