Leetcode 2833: Furthest Point From Origin
You are given a string moves consisting of characters ‘L’, ‘R’, and ‘’. The string represents movements on a number line starting from position 0. You can choose to move left or right when the character is ‘’, and the goal is to calculate the maximum distance from the origin you can reach after completing all the moves.
Problem
Approach
Steps
Complexity
Input: The input consists of a string moves where each character is either 'L', 'R', or '_'.
Example: moves = 'L_RL__R'
Constraints:
• 1 <= moves.length <= 50
• moves consists only of characters 'L', 'R', and '_'.
Output: Return the maximum distance from the origin that can be achieved after completing all the moves.
Example: 3
Constraints:
• The output should be a single integer representing the maximum distance.
Goal: To calculate the maximum distance from the origin after performing all moves, accounting for the choices made at each '_' character.
Steps:
• Initialize two counters to track the furthest left and right positions based on the current moves.
• Iterate over the string moves and calculate the maximum possible distance considering the '_' characters can be either 'L' or 'R'.
• Return the maximum of the absolute values of the two positions.
Goal: The input string moves has constraints as follows:
Steps:
• 1 <= moves.length <= 50
• moves consists only of characters 'L', 'R', and '_'.
Assumptions:
• The characters '_' in the moves string are flexible and can be treated as either 'L' or 'R'.
• Input: moves = 'L_RL__R'
• Explanation: The furthest point we can reach is -3 after making the sequence of moves 'LLRLLLR'.
• Input: moves = '_R__LL_'
• Explanation: The furthest point we can reach is -5 after making the sequence 'LRLLLLL'.
Approach: The problem can be approached by iterating through the string and calculating the furthest points we can reach for both left and right moves, considering the flexibility provided by '_' characters.
Observations:
• For every '_' character, we can choose either left or right, so we need to maximize the distance considering both choices.
• We should compute the furthest left and right points and then take the maximum of their absolute values.
Steps:
• Initialize two variables, one for tracking the leftmost distance and another for tracking the rightmost distance.
• Iterate over the string moves, updating both left and right distances as you encounter 'L', 'R', and '_'.
• For each '_', update both distances by considering it as 'L' and 'R' respectively.
• Return the maximum of the absolute values of the two distances.
Empty Inputs:
• If the input string is empty, the distance should be 0.
Large Inputs:
• The solution should handle the case where the string length is large (up to 50 characters).
Special Values:
• If the string contains only 'L' or 'R' characters, the solution will still compute the correct result.
Constraints:
• Ensure that the solution runs efficiently given the constraints on the length of the moves string.
int furthestDistanceFromOrigin(string moves) {
int n=moves.length();
int l=0, r=0;
for(int i=0;i<n;i++){
if(moves[i]=='L' || moves[i]=='_'){
l--;
}else{
l++;
}
if(moves[i]=='R' || moves[i]=='_'){
r++;
}else{
r--;
}
}
if(l<0) l *= -1;
if(r<0) r *= -1;
return max(l,r);
}
1 : Variable Declaration
int furthestDistanceFromOrigin(string moves) {
Defines the function `furthestDistanceFromOrigin`, which takes a string `moves` as input to determine the furthest distance from the origin.
2 : Length Calculation
int n=moves.length();
Calculates the length of the `moves` string to determine how many steps to process.
3 : Variable Initialization
int l=0, r=0;
Initializes two integer variables `l` and `r` to track the left and right movements respectively.
4 : Loop Setup
for(int i=0;i<n;i++){
Starts a loop that iterates through each character in the `moves` string.
5 : Left Movement Check
if(moves[i]=='L' || moves[i]=='_'){
Checks if the current move is left ('L') or an underscore ('_') which signifies movement towards the left.
6 : Left Movement
l--;
Decreases the left movement counter `l` when a left move is detected.
7 : Else Right Movement Check
}else{
Otherwise, check if the move is towards the right.
8 : Right Movement
l++;
Increases the left movement counter `l` if the move is not left.
9 : Right Movement Check
if(moves[i]=='R' || moves[i]=='_'){
Checks if the current move is right ('R') or an underscore ('_') which signifies movement towards the right.
10 : Right Movement
r++;
Increases the right movement counter `r` when a right move is detected.
11 : Else Left Movement Check
}else{
Otherwise, check if the move is towards the left.
12 : Left Movement
r--;
Decreases the right movement counter `r` if the move is not right.
13 : Negative Value Correction
if(l<0) l *= -1;
Corrects the left movement counter `l` if it is negative by multiplying it by -1 to ensure positive values.
14 : Negative Value Correction
if(r<0) r *= -1;
Corrects the right movement counter `r` if it is negative by multiplying it by -1 to ensure positive values.
15 : Return Result
Space for additional logic if needed.
16 : Return Maximum
return max(l,r);
Returns the maximum of the left and right movement values, representing the furthest distance from the origin.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is linear in the length of the moves string since we only iterate once over the string.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant, as we only need a few variables to track the distances.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus