Maximum Manhattan Distance After All Moves - Solution & Explanation

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.