Furthest Point From Origin solution and explanation
Google
9 more videos on this problem
Furthest Point From Origin | Simple Explanation | Dry Run | Leetcode 2833 | codestorywithMIKcodestorywithMIK · 12:33 · 3K views
2833. Furthest Point From Origin (Leetcode Easy)Programming Live with Larry · 4:20 · 454 views
Furthest Point From Origin | Leetcode 2833 | Contest 360Tech Courses · 4:52 · 416 views
Leetcode 2833 || Furthest Point From Origin || Leetcode Weekly Easy || cppKomal Pal · 9:46 · 288 views
2833. Furthest Point From Origin | Leetcode Daily - PythonLeetcode Daily · 4:09 · 246 views
Furthest Point From Origin | Leetcode 2833 | Java HindiKernel Queen 👑 · 3:50 · 186 views
LeetCode 2833. Furthest Point From Origin | Java Solution | EasyMichael Herman · 7:01 · 152 views
Leetcode 2833 Furthest Point From OriginTech Diet · 2:37 · 145 views
Furthest Point From Origin | LeetCode 2833 - Pythonimpoldev · 5:05 · 107 views
Furthest Point From Origin | Leetcode - 2833Shivam Gupta · 10:34 · 43 views
The problem
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 ith move, you can choose one of the following directions:
- move to the left if
moves[i] = 'L'ormoves[i] = '_' - move to the right if
moves[i] = 'R'ormoves[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".
Constraints:
1 <= moves.length == n <= 50movesconsists only of characters'L','R'and'_'.
Approach overview
Problem Overview: You start at position 0 on a number line and execute a sequence of moves represented by a string. L moves left, R moves right, and _ can be either. The goal is to assign each underscore optimally so the final position is as far from the origin as possible.
Approach 1: Maximize L and R Separately (O(n) time, O(1) space)
Scan the string once and count how many L, R, and _ characters appear. The final position after fixed moves is R - L. Each underscore can be converted to either direction, so the trick is to push the position further from zero. You compute two possibilities: treat all underscores as R or treat all underscores as L. That gives distances |(R + _) - L| and |R - (L + _)|. The maximum of these two values is the furthest point reachable. This works because every underscore contributes exactly one step and the optimal strategy is to move consistently in the direction that increases absolute displacement.
Approach 2: Simulate Movement with Maximum Flexibility (O(n) time, O(1) space)
Instead of evaluating two scenarios explicitly, track the current displacement while scanning the string. Increase a counter for R, decrease it for L, and count underscores separately. After processing the entire string, the fixed displacement is pos and you have blank flexible moves. The maximum possible distance from the origin becomes |pos| + blank. Each underscore can always extend the current direction of movement, so they simply add to the absolute displacement. This approach expresses the same idea as the previous one but with fewer intermediate calculations.
Both approaches rely on simple string traversal and basic counting. No extra data structures are needed because the order of operations does not affect the final displacement—only the counts of each move type matter.
Recommended for interviews: The counting-based formula from Approach 2 is what interviewers typically expect. It shows you recognized that underscores are flexible moves and that maximizing the absolute displacement reduces to |R - L| + _. Explaining Approach 1 first can demonstrate reasoning about edge cases, but the simplified formula proves you spotted the core pattern quickly.
Approach 1: Approach 1: Maximize L and R Separately
In this approach, you need to count the maximum distance from the origin both in the negative and positive directions independently. For each 'L', decrease the position, for each 'R', increase the position and for '_', consider both possibilities of increment or decrement. Finally, take the maximum of the absolute values of these two calculated distances.
def furthest_distance(moves):
left_count = moves.count('L') + moves.count('_')
right_count = moves.count('R') + moves.count('_')
return max(left_count, right_count)
# Example usage
print(furthest_distance('L_RL__R')) # Output: 3
print(furthest_distance('_R__LL_')) # Output: 5
print(furthest_distance('_______')) # Output: 7public class FurthestDistance {
public static int furthestDistance(String moves) {
int leftCount = 0;
int rightCount = 0;
for (int i = 0; i < moves.length(); i++) {
if (moves.charAt(i) == 'L' || moves.charAt(i) == '_') {
leftCount++;
}
if (moves.charAt(i) == 'R' || moves.charAt(i) == '_') {
rightCount++;
}
}
return Math.max(leftCount, rightCount);
}
public static void main(String[] args) {
System.out.println(furthestDistance("L_RL__R")); // Output: 3
System.out.println(furthestDistance("_R__LL_")); // Output: 5
System.out.println(furthestDistance("_______")); // Output: 7
}
}#include <iostream>
#include <string>
#include <algorithm>
int furthest_distance(const std::string& moves) {
int left_count = std::count(moves.begin(), moves.end(), 'L') + std::count(moves.begin(), moves.end(), '_');
int right_count = std::count(moves.begin(), moves.end(), 'R') + std::count(moves.begin(), moves.end(), '_');
return std::max(left_count, right_count);
}
int main() {
std::cout << furthest_distance("L_RL__R") << std::endl; // Output: 3
std::cout << furthest_distance("_R__LL_") << std::endl; // Output: 5
std::cout << furthest_distance("_______") << std::endl; // Output: 7
return 0;
}function furthestDistance(moves) {
let leftCount = 0;
let rightCount = 0;
for (let i = 0; i < moves.length; i++) {
if (moves[i] === 'L' || moves[i] === '_') {
leftCount++;
}
if (moves[i] === 'R' || moves[i] === '_') {
rightCount++;
}
}
return Math.max(leftCount, rightCount);
}
console.log(furthestDistance('L_RL__R')); // Output: 3
console.log(furthestDistance('_R__LL_')); // Output: 5
console.log(furthestDistance('_______')); // Output: 7;using System;
class FurthestPoint {
public static int FurthestDistance(string moves) {
int leftCount = 0;
int rightCount = 0;
foreach (char move in moves) {
if (move == 'L' || move == '_') {
leftCount++;
}
if (move == 'R' || move == '_') {
rightCount++;
}
}
return Math.Max(leftCount, rightCount);
}
static void Main() {
Console.WriteLine(FurthestDistance("L_RL__R")); // Output: 3
Console.WriteLine(FurthestDistance("_R__LL_")); // Output: 5
Console.WriteLine(FurthestDistance("_______")); // Output: 7
}
}This Python function uses the count method to calculate the potential maximum steps in both the left and right directions. The total steps towards the left (negative direction) can be the sum of 'L' and '_', while the total steps towards the right (positive direction) can be the sum of 'R' and '_'. The answer will be the maximum of these two values.
Time Complexity: O(n), where n is the length of the string, as we are iterating over the string a few times.
Space Complexity: O(1), as we are using a fixed amount of additional space.
Approach 2: Approach 2: Simulate Movement with Maximum Flexibility
This approach uses a simulation strategy, keeping track of two possibilities: one favoring maximum left movement and the other favoring maximum right movement from the start. By iterating once, adjust both positions based on the character read, choosing left or right for the underscore as needed.
def furthest_distance(moves):
max_left, max_right = 0, 0
for move in moves:
if move == 'L':
max_left -= 1
max_right -= 1
elif move == 'R':
max_left += 1
max_right += 1
elif move == '_':
max_left -= 1
max_right += 1
return max(abs(max_left), max_right)
print(furthest_distance('L_RL__R')) # Output: 3
print(furthest_distance('_R__LL_')) # Output: 5
print(furthest_distance('_______')) # Output: 7public class FurthestDistance {
public static int furthestDistance(String moves) {
int maxLeft = 0, maxRight = 0;
for (char move : moves.toCharArray()) {
if (move == 'L') {
maxLeft--;
maxRight--;
} else if (move == 'R') {
maxLeft++;
maxRight++;
} else if (move == '_') {
maxLeft--;
maxRight++;
}
}
return Math.max(Math.abs(maxLeft), maxRight);
}
public static void main(String[] args) {
System.out.println(furthestDistance("L_RL__R")); // Output: 3
System.out.println(furthestDistance("_R__LL_")); // Output: 5
System.out.println(furthestDistance("_______")); // Output: 7
}
}#include <iostream>
#include <string>
#include <algorithm>
int furthest_distance(const std::string& moves) {
int max_left = 0, max_right = 0;
for (char move : moves) {
if (move == 'L') {
--max_left;
--max_right;
} else if (move == 'R') {
++max_left;
++max_right;
} else if (move == '_') {
--max_left;
++max_right;
}
}
return std::max(std::abs(max_left), max_right);
}
int main() {
std::cout << furthest_distance("L_RL__R") << std::endl; // Output: 3
std::cout << furthest_distance("_R__LL_") << std::endl; // Output: 5
std::cout << furthest_distance("_______") << std::endl; // Output: 7
return 0;
}function furthestDistance(moves) {
let maxLeft = 0, maxRight = 0;
for (let move of moves) {
if (move === 'L') {
maxLeft--;
maxRight--;
} else if (move === 'R') {
maxLeft++;
maxRight++;
} else if (move === '_') {
maxLeft--;
maxRight++;
}
}
return Math.max(Math.abs(maxLeft), maxRight);
}
console.log(furthestDistance('L_RL__R')); // Output: 3
console.log(furthestDistance('_R__LL_')); // Output: 5
console.log(furthestDistance('_______')); // Output: 7;using System;
class FurthestPoint {
public static int FurthestDistance(string moves) {
int maxLeft = 0, maxRight = 0;
foreach (char move in moves) {
if (move == 'L') {
maxLeft--;
maxRight--;
} else if (move == 'R') {
maxLeft++;
maxRight++;
} else if (move == '_') {
maxLeft--;
maxRight++;
}
}
return Math.Max(Math.Abs(maxLeft), maxRight);
}
static void Main(string[] args) {
Console.WriteLine(FurthestDistance("L_RL__R")); // Output: 3
Console.WriteLine(FurthestDistance("_R__LL_")); // Output: 5
Console.WriteLine(FurthestDistance("_______")); // Output: 7
}
}The above Python implementation mimics potential movement paths by simulating two cores: one prioritizing left steps for `_` initially, and the other prioritizing right steps. At each underscore, the left pathway decreases and the right pathway increases, allowing flexibility to achieve the maximum distance in the end calculation.
Time Complexity: O(n), as it loops once through the string.
Space Complexity: O(1), as no additional structures with a size dependency on input length are used.
Approach 3: Greedy
When encountering the character '', we can choose to move left or right. The problem requires us to find the farthest point from the origin. Therefore, we can first traverse once, greedily move all '' to the left, and find the farthest point from the origin at this time. Then traverse again, greedily move all '_' to the right, and find the farthest point from the origin at this time. Finally, take the maximum of the two traversals.
Further, we only need to calculate the difference between the number of 'L' and 'R' in the string, and then add the number of '_'.
The time complexity is O(n), where n is the length of the string. The space complexity is O(1).
function furthestDistanceFromOrigin(moves: string): number {
const count = (c: string) => moves.split('').filter(x => x === c).length;
return Math.abs(count('L') - count('R')) + count('_');
}func furthestDistanceFromOrigin(moves string) int {
count := func(c string) int { return strings.Count(moves, c) }
return abs(count("L")-count("R")) + count("_")
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Maximize L and R Separately | Time Complexity: O(n), where n is the length of the string, as we are iterating over the string a few times. |
| Approach 2: Simulate Movement with Maximum Flexibility | Time Complexity: O(n), as it loops once through the string. |
| Greedy | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Maximize L and R Separately | O(n) | O(1) | Clear reasoning approach when explaining both extreme assignments of '_' characters. |
| Simulate Movement with Maximum Flexibility | O(n) | O(1) | Preferred solution in interviews; reduces the problem to |R-L| + underscore count. |
Frequently asked questions
Is Furthest Point From Origin easy or hard?
Furthest Point From Origin is classified as an Easy problem. The challenge is recognizing that underscore moves can always extend the current displacement, which simplifies the final formula to |R - L| plus the number of underscores.
Furthest Point From Origin Python/Java solution
In both Python and Java, iterate through the string and maintain counters for L, R, and _. After the loop, return Math.abs(R - L) + underscore_count (or abs(R - L) + underscores in Python). The logic is identical across languages and runs in linear time.
How to solve Furthest Point From Origin in O(n)?
Traverse the string and count L, R, and _ characters. Compute the base displacement as R - L. Since each underscore can be assigned to extend movement in the favorable direction, the maximum distance from the origin equals |R - L| + underscores. This requires a single pass over the string.
What is the best approach for Furthest Point From Origin?
The optimal approach counts how many L, R, and _ characters appear in the string. The fixed displacement is R - L, and each underscore can extend the movement in the direction that increases the absolute value. The final answer becomes |R - L| + number_of_underscores. This runs in O(n) time with O(1) extra space.
Is Furthest Point From Origin asked at Google/Amazon/Meta?
This problem reflects a common interview pattern involving greedy reasoning and counting. Variations of flexible-move or maximize-displacement problems appear in interviews at companies like Amazon and Google, especially in early screening rounds focused on string processing and reasoning.
What data structure is used in Furthest Point From Origin?
No complex data structure is needed. The solution uses simple counters while iterating through the string. The key idea comes from counting characters and applying a greedy observation about maximizing absolute displacement.
What is the time complexity of Furthest Point From Origin?
The solution runs in O(n) time because the string is scanned once to count moves. Space complexity is O(1) since only a few integer counters are stored. No additional data structures are required.