Where were u these days. Happy to see you back. The day u posted ur last video, I got placed. I wanted to tell u this. Once I was a zero in coding. Ur videos motivated me to code. Thank you Neetcode.
Great Job! To be fair, you don't really need to be that familiar with linear algebra. The way I have always thought about it esp. during middle school is to use the coordinate plane. Draw a coordinate plane and label it appropriately with -x , +x, -y, and +y (We will only looking at +x and +y in the end) . Now say you are rotating 90 degree counterclockwise. So -x , +x, -y, and +y will be shifted to the "label" which is to their immediate left. That is, -x shifts 90 counterclockwise to become -y; -y shifts similarly to become +x; +x shifts to become +y; and +y shifts to become -x. Now, if you read your + x and +y axes, you have new labels which are -y and x respectively. In essence, you have rotated the entire plane by 90 degree counterclockwise. This works for every angle for which there is a utility in performing this exercise.
You’re welcome guys! The easiest approaches are always better than the esoteric ones. People can do programming without linear algebra. I’m considering starting a TH-cam channel to teach programming, starting with C and then transitioning gently to C++.
This is what I came up with in my first try without looking any hints [Beats 98%]: def isRobotBounded(self, instructions: str) -> bool: pos = [0,0] direction = 'N' directions = ['N', 'E', 'S', 'W'] for t in range(4): for i in range(len(instructions)): if instructions[i] == 'G': if direction == 'N': pos[1]+=1 elif direction == 'W': pos[0]-=1 elif direction == 'S': pos[1]-=1 elif direction == 'E': pos[0]+=1 elif instructions[i] == 'L': index = directions.index(direction) direction = directions[(index+3)%4] elif instructions[i] == 'R': index = directions.index(direction) direction = directions[(index+1)%4] if pos == [0,0] and i == len(instructions)-1: return True return False
For anyone having trouble with the direction thing : Take a vector (x,y) and note that the vector (-y,x) is perpendicular since their inner product is zero : -xy+yx = 0. But also (y,-x) is perpendicular since inner product is xy-yx=0. Left rotation means that your new vector points to the left and so its x coordinate decreases when walking to that direction and thus the - sign.
Cleanest solution to the problem I have seen. Definitely helps that you explained the thinking process instead of us having to glean the reasoning behind some of the conditional checks in the for loop.
man, you won't believe how much I like your videos. I literally just attempt a question only if you have made a video on it. Thanks bro, I wish youtube had more good channels like this!
what an elegant code and what a profound thought process - after struggling to understand the mathematical intuition and finally getting the intuition, I watched your code and I am taken aback by the simplicity of the thought process - thank you so much for sharing it.
Thank you for the explaination! Although I still have one question after going through the video s few times, I wonder why it is guaranteed to be a cycle if the direction changes after one iteration over the instructions? Is it not possible that even if the direction changed but in the end it could never go back to the posistion (0,0)? Would highly appreciate if someone could help me with my confusion! Thanks in advance!
No , while executing one instruction set if the final direction changes from the initial one so it means that for every instruction set the direction is gonna change , so as we have only limited number of directions (only 4) , it is inevitable that the robot will move to its initial position once .
He showed you multiple examples, but just try to imagine it for yourself. If the net direction change is just one turn, then in loop 3, the robot is now undoing everything it already did in loop 1. And then loop 4 will undo loop 2, so you're back at the start. Remember that if there is only one turn, After the 2nd loop the robot is now facing the opposite direction from the beginning, so it will start undoing it's actions since the forward distance is the same every time.
Watched thanks Idea is that if after applying the moves once, the robot is back at the origin then definitely stuck on a loop. If the robot is not at origin but the direction changed from the initial direction then the robot will be in a loop when we apply the instructions infinitely. We return (x,y) == (0,0) || directionChanged after applying the instructions once
how to deduce that changing direction in any position whether south, west, east is going to end up a circle , is there a mathematical proof behind this?
Great explanation! I have a small doubt about the rotation. On the left rotation, it seems to me we only change sign when we switch from the Oy to Ox. Let's say we are in the initial position, facing north - encoded (0,1). If we rotate left, we will be facing west - encoded (-1,0). So far so good. If we do another left rotation, we will be facing south - encoded (0,-1) => we did not change sign!!! Essentially we change signs only when we go from N to W and S to E. The other two, W to S and E to N, do not change signs! Am I missing something here?
we are facing west i.e (-1,0). So if we rotate left again, first we need to swap values so it would be (0,-1). Next would be to put negative sign on X parameter. Since 0 cant be negative its zero only. so south would be (0,-1)
It still works. In the other two directions, the the y coordinate is zero, so when you make x into -y, it becomes -0, which is still 0. No issues at all with the code.
To think about which direction the robot is rotating, you can simply think about the 4 quadrant signs of quadrants I-IV learned in middle school algebra.
Can somebody explain the math behind or post the link where somebody has explained? Everything is clear except the last 2 if cases. Cannot understand the Math behind or how you've arrived at those formulae.
Case 1 : initially the robot was at (0, 0) position. if the final position (after executing all commands) is also (0, 0) means, it can't go out of bound even after infinite loops. Case 2 : Assume the robot moved from the top end of "L" to the bottom right side of “L", it's direction got changee. So after 4 times executing the same commands it will reach the top end of "L", completing a square. So it can't go out of bound if the direction got changed.
I wonder is there any way that makes a path spiral then what will be the case it will be return true by ur code because it will change direction but i don't think it is a circular
Try as you might, the robot will return to its starting position if the final direction is south, east or west. For example, if after the first round the robot ends up at (x + a, y + b) and facing east, then in the next iterations it will end up at (x + a + b, y + b − a) → (x + b, y − a) → (x, y), back where it started! Since the choice of the displacement (a, b) was arbitrary, this always happens. You can convince yourself of the other directions (facing south and west) similarly.
I've seen that if there is no L on the string, robot goes on unidirectionally indefinitely, but even if there is one L, the robot eventually gets stuck in an infinite loop if the robot is instructed to move on infinitely.
@@tcal208 no I think the robot doesn't repeat the forward instruction only. After RG it will execute another RG and go right and 1 unit forward, and keep on repeating RG until a unit size square is formed thus satisfying the break condition.
Another great video!! I'm really having trouble following the python specific syntax sugar though. (dirX, dirY) != (0, 1) , is this read as (dirX != 0 && dirY != 1) or is it read as (dirX != 0 || dirY != 1), I would love a more non-pythony way of doing things so non pythoners can keep up, thanks!!
Can someone please explain the logic behind his two conditions: 1) change in position, if position didn't change. 2) change in direction , if position did change and direction change. if one of those conditions is true, then we have a cycle. How :
1) Well if you come back to the same position after a single run i.e. back to the origin that means no matter what direction you are facing before each run, you will always end up back at the origin. You can think of it as a closed-loop circuit that always ends up where you start (no matter the direction because if its true for north, no reason why it would not be equally true for east, west or south). 2) This says that after one run, if your direction is not north (which is always our starting direction), then you are also in a loop. If you end up facing south, then the loop size is 2 (i.e. you will be back at the origin after 2 runs). If you end up facing left or right, then the loop size is 4. Anybody who has driven without Maps in a new area knows this :D Both of these were not obvious to me frankly. I always felt uncertain that there might be edge cases I am not thinking about. In fact being sure of this is the trickiest part of this question for me.
@@siqb I JUST started this problem so maybe I haven't beat my head up against it enough to understand what's going on. But let's say that you have a test case in which you have directions like "LGRG" OR "RGLG" (that fits both criteria to return true according to this video and what you just stated). If you mapped that out on a 2D plane, it definitely doesn't stay within a finite circle if it runs infinitely. A loop? Sure. But not within a circle
The first condition is needed because supposed you have GG LL GG LL After 4 Left turns, you are facing north. And according toe condition 2, facing north at the end means you move forward forever (no loop). So you need to first check if you actually just end up at (0,0) at the start of every loop. Then it won't matter that you're facing north. However, if you end up anywhere else, then facing north at the end means you never come back to the start, and not facing north means you will come back in either 2 or 4 loops.
Just ran the same code and it works, pasted it below, let me know if it still gives error: class Solution: def isRobotBounded(self, instructions: str) -> bool: dirX, dirY = 0, 1 x, y = 0, 0 for d in instructions: if d == "G": x, y = x + dirX, y + dirY elif d == "L": dirX, dirY = -1*dirY, dirX else: dirX, dirY = dirY, -1*dirX return (x, y) == (0, 0) or (dirX, dirY) != (0, 1)
It's not a position, it's a direction that robot is facing initially. Since robot facing North, then the direction is (0, 1) the initial position is x, y = 0, 0
Surprisingly same Java code fails on leetcode. Following is my code snippet that's failing on LettCode. class Solution { public boolean isRobotBounded(String instructions) { // Initially we are facing to North int dirX = 0, dirY = 1; // We start at origin int x = 0, y = 0; for (char ch : instructions.toCharArray()) { if (ch == 'G') { x = x + dirX; y = y + dirY; } else if (ch == 'L') { int temp = dirX; dirX = -dirY; dirY = temp; } else{ int temp = dirX; dirX = dirY; dirY = -temp; } } // after one cycle: // robot returns into initial position // or robot has changed direction return (x == 0 && y == 0) || (dirX !=0 && dirY != 1); } }
Brother, It's not so challenging to look at the hints and answer. Can you explain exactly why does change in direction conclude that the pattern will create a circle? In the interviews, such hints will not be given.
And takes longer. And shows a lack of optimization skills. The hiring manager won't like that. They'll have to worry that every time you get a task, you might brute force with O(n^2) or O(n!) solutions because you feel it's more intuitive. Software engineers get paid to engineer.
It's so disheartening to see just 1 like in 20 hours ,I request all to please atleast leave a like , a like doesn't cost anything , but someone's efforts does .
Where were u these days. Happy to see you back. The day u posted ur last video, I got placed. I wanted to tell u this. Once I was a zero in coding. Ur videos motivated me to code. Thank you Neetcode.
That's awesome news, I'm happy to hear it! Your hard work paid off, congrats! :)
Great Job!
To be fair, you don't really need to be that familiar with linear algebra. The way I have always thought about it esp. during middle school is to use the coordinate plane. Draw a coordinate plane and label it appropriately with -x , +x, -y, and +y (We will only looking at +x and +y in the end) . Now say you are rotating 90 degree counterclockwise. So -x , +x, -y, and +y will be shifted to the "label" which is to their immediate left. That is, -x shifts 90 counterclockwise to become -y; -y shifts similarly to become +x; +x shifts to become +y; and +y shifts to become -x. Now, if you read your + x and +y axes, you have new labels which are -y and x respectively. In essence, you have rotated the entire plane by 90 degree counterclockwise. This works for every angle for which there is a utility in performing this exercise.
Thank you. I could not understand the linear algebra thing.
Thanks so much for this!
You’re welcome guys! The easiest approaches are always better than the esoteric ones. People can do programming without linear algebra. I’m considering starting a TH-cam channel to teach programming, starting with C and then transitioning gently to C++.
Best Leetcode videos on the internet
This is what I came up with in my first try without looking any hints [Beats 98%]:
def isRobotBounded(self, instructions: str) -> bool:
pos = [0,0]
direction = 'N'
directions = ['N', 'E', 'S', 'W']
for t in range(4):
for i in range(len(instructions)):
if instructions[i] == 'G':
if direction == 'N':
pos[1]+=1
elif direction == 'W':
pos[0]-=1
elif direction == 'S':
pos[1]-=1
elif direction == 'E':
pos[0]+=1
elif instructions[i] == 'L':
index = directions.index(direction)
direction = directions[(index+3)%4]
elif instructions[i] == 'R':
index = directions.index(direction)
direction = directions[(index+1)%4]
if pos == [0,0] and i == len(instructions)-1:
return True
return False
For anyone having trouble with the direction thing :
Take a vector (x,y) and note that the vector (-y,x) is perpendicular since their inner product is zero :
-xy+yx = 0.
But also (y,-x) is perpendicular since inner product is xy-yx=0.
Left rotation means that your new vector points to the left and so its x coordinate decreases when walking to that direction and thus the - sign.
Cleanest solution to the problem I have seen. Definitely helps that you explained the thinking process instead of us having to glean the reasoning behind some of the conditional checks in the for loop.
man, you won't believe how much I like your videos. I literally just attempt a question only if you have made a video on it. Thanks bro, I wish youtube had more good channels like this!
Saaaame
what an elegant code and what a profound thought process - after struggling to understand the mathematical intuition and finally getting the intuition, I watched your code and I am taken aback by the simplicity of the thought process - thank you so much for sharing it.
Thank you for the explaination! Although I still have one question after going through the video s few times, I wonder why it is guaranteed to be a cycle if the direction changes after one iteration over the instructions? Is it not possible that even if the direction changed but in the end it could never go back to the posistion (0,0)? Would highly appreciate if someone could help me with my confusion! Thanks in advance!
No , while executing one instruction set if the final direction changes from the initial one so it means that for every instruction set the direction is gonna change , so as we have only limited number of directions (only 4) , it is inevitable that the robot will move to its initial position once .
He showed you multiple examples, but just try to imagine it for yourself. If the net direction change is just one turn, then in loop 3, the robot is now undoing everything it already did in loop 1. And then loop 4 will undo loop 2, so you're back at the start.
Remember that if there is only one turn, After the 2nd loop the robot is now facing the opposite direction from the beginning, so it will start undoing it's actions since the forward distance is the same every time.
Watched thanks
Idea is that if after applying the moves once, the robot is back at the origin then definitely stuck on a loop. If the robot is not at origin but the direction changed from the initial direction then the robot will be in a loop when we apply the instructions infinitely.
We return (x,y) == (0,0) || directionChanged after applying the instructions once
I find it hard to prove to myself that if we are in a new posn with a different direction we will always end up at the origin
Thankyou again for all your videos and amazing explanation. This is the easiest explanation I ever saw to this problem!!
Thank you for all the solved problems and clear explanations :)
NEW COLLECTION! Thanks!!
how to deduce that changing direction in any position whether south, west, east is going to end up a circle , is there a mathematical proof behind this?
I swear, if I get a job, it will be only because of NeetCode's incredible explanation!
Did it work
bro u gotta update us
Great explanation! I have a small doubt about the rotation. On the left rotation, it seems to me we only change sign when we switch from the Oy to Ox. Let's say we are in the initial position, facing north - encoded (0,1). If we rotate left, we will be facing west - encoded (-1,0). So far so good. If we do another left rotation, we will be facing south - encoded (0,-1) => we did not change sign!!! Essentially we change signs only when we go from N to W and S to E. The other two, W to S and E to N, do not change signs! Am I missing something here?
I agree with you, i think the rotation has a bug in the code
what do you mean when you say we did not change sign
we are facing west i.e (-1,0). So if we rotate left again, first we need to swap values so it would be (0,-1). Next would be to put negative sign on X parameter. Since 0 cant be negative its zero only. so south would be (0,-1)
It still works. In the other two directions, the the y coordinate is zero, so when you make x into -y, it becomes -0, which is still 0. No issues at all with the code.
The rule for a rotation by 90° about the origin is (x,y)→(−y,x)
Only applies to the left turn
You are awesome... Thank you man...
Thank you for the effort to make this videos!
To think about which direction the robot is rotating, you can simply think about the 4 quadrant signs of quadrants I-IV learned in middle school algebra.
Was waiting for some time, thank you for all the effort you put in! Motivates a ton!
9:35 how did your application at freddie mac go? :p
😳
@@NeetCode lmao!
Happy to see you back !!! was waiting for your videos....
Finally! Hope you are doing well and alright! :D
Can somebody explain the math behind or post the link where somebody has explained? Everything is clear except the last 2 if cases. Cannot understand the Math behind or how you've arrived at those formulae.
Case 1 : initially the robot was at (0, 0) position. if the final position (after executing all commands) is also (0, 0) means, it can't go out of bound even after infinite loops.
Case 2 : Assume the robot moved from the top end of "L" to the bottom right side of “L", it's direction got changee. So after 4 times executing the same commands it will reach the top end of "L", completing a square. So it can't go out of bound if the direction got changed.
I wonder is there any way that makes a path spiral then what will be the case it will be return true by ur code because it will change direction but i don't think it is a circular
Try as you might, the robot will return to its starting position if the final direction is south, east or west. For example, if after the first round the robot ends up at (x + a, y + b) and facing east, then in the next iterations it will end up at (x + a + b, y + b − a) → (x + b, y − a) → (x, y), back where it started! Since the choice of the displacement (a, b) was arbitrary, this always happens. You can convince yourself of the other directions (facing south and west) similarly.
I've seen that if there is no L on the string, robot goes on unidirectionally indefinitely, but even if there is one L, the robot eventually gets stuck in an infinite loop if the robot is instructed to move on infinitely.
"RG" -> no L still in a loop.
"GLGRG" -> L but robot is never stuck in an infinite loop.
@@tcal208 no it says G makes it go 1 unit only
@@Akaash449 but the robot repeats it for ever, I don't get your point either way
@@tcal208 no I think the robot doesn't repeat the forward instruction only. After RG it will execute another RG and go right and 1 unit forward, and keep on repeating RG until a unit size square is formed thus satisfying the break condition.
@@Akaash449 Which means, the robot is bound to a circle in the plane, thus the "no L but still in a loop".
Another great video!! I'm really having trouble following the python specific syntax sugar though. (dirX, dirY) != (0, 1) , is this read as (dirX != 0 && dirY != 1) or is it read as (dirX != 0 || dirY != 1), I would love a more non-pythony way of doing things so non pythoners can keep up, thanks!!
java solution:
public boolean isRobotBounded(String instructions) {
int[] dir = new int[]{1,0};
int[] pos = new int[]{0,0};
char ch[] = instructions.toCharArray();
for(char c : ch){
if(c=='G'){
pos[0]+=dir[0];
pos[1]+=dir[1];
}else if(c=='L'){
int temp = dir[0];
dir[0] = -1*dir[1];
dir[1] = temp;
}else{
int temp = dir[1];
dir[1] = -1*dir[0];
dir[0] = temp;
}
}
return (pos[0]==0&&pos[1]==0) || (dir[0]!=1 || dir[1]!=0);
}
It should be (x==0&&y==0)||(dirX!=0||dirY!=1). Suppose, A=(dirX,dirY), B=(0,1). So it's checking whether A!=B
Can someone please explain the logic behind his two conditions:
1) change in position, if position didn't change.
2) change in direction , if position did change and direction change.
if one of those conditions is true, then we have a cycle. How :
1) Well if you come back to the same position after a single run i.e. back to the origin that means no matter what direction you are facing before each run, you will always end up back at the origin. You can think of it as a closed-loop circuit that always ends up where you start (no matter the direction because if its true for north, no reason why it would not be equally true for east, west or south).
2) This says that after one run, if your direction is not north (which is always our starting direction), then you are also in a loop. If you end up facing south, then the loop size is 2 (i.e. you will be back at the origin after 2 runs). If you end up facing left or right, then the loop size is 4. Anybody who has driven without Maps in a new area knows this :D
Both of these were not obvious to me frankly. I always felt uncertain that there might be edge cases I am not thinking about. In fact being sure of this is the trickiest part of this question for me.
@@siqb I JUST started this problem so maybe I haven't beat my head up against it enough to understand what's going on.
But let's say that you have a test case in which you have directions like "LGRG" OR "RGLG" (that fits both criteria to return true according to this video and what you just stated). If you mapped that out on a 2D plane, it definitely doesn't stay within a finite circle if it runs infinitely. A loop? Sure. But not within a circle
LMAO nevermind, I just re-read the part in the second condition that specifies "not facing north" at the end of the loop. Makes sense now
@@siqb thank you man.
The first condition is needed because supposed you have GG LL GG LL
After 4 Left turns, you are facing north. And according toe condition 2, facing north at the end means you move forward forever (no loop). So you need to first check if you actually just end up at (0,0) at the start of every loop. Then it won't matter that you're facing north. However, if you end up anywhere else, then facing north at the end means you never come back to the start, and not facing north means you will come back in either 2 or 4 loops.
its showing wrong on leet code if i type exactly same code that you have here..
Just ran the same code and it works, pasted it below, let me know if it still gives error:
class Solution:
def isRobotBounded(self, instructions: str) -> bool:
dirX, dirY = 0, 1
x, y = 0, 0
for d in instructions:
if d == "G":
x, y = x + dirX, y + dirY
elif d == "L":
dirX, dirY = -1*dirY, dirX
else:
dirX, dirY = dirY, -1*dirX
return (x, y) == (0, 0) or (dirX, dirY) != (0, 1)
I didn't get the point where initially dirx, diry=0,1 where as im standing at 0,0
It's not a position, it's a direction that robot is facing initially.
Since robot facing North, then the direction is (0, 1)
the initial position is x, y = 0, 0
Surprisingly same Java code fails on leetcode.
Following is my code snippet that's failing on LettCode.
class Solution {
public boolean isRobotBounded(String instructions) {
// Initially we are facing to North
int dirX = 0, dirY = 1;
// We start at origin
int x = 0, y = 0;
for (char ch : instructions.toCharArray()) {
if (ch == 'G') {
x = x + dirX;
y = y + dirY;
}
else if (ch == 'L') {
int temp = dirX;
dirX = -dirY;
dirY = temp;
}
else{
int temp = dirX;
dirX = dirY;
dirY = -temp;
}
}
// after one cycle:
// robot returns into initial position
// or robot has changed direction
return (x == 0 && y == 0) || (dirX !=0 && dirY != 1);
}
}
return (x == 0 && y == 0) || (dirX != 0 || dirY != 1) ;
same here.. failing in Java, any fixes?
if ((x==0 && y==0) || dirX != 0 || dirY != 1) return true; else return false;
return (x==0 && y==0) || dirX != 0 || dirY != 1;
Brother, It's not so challenging to look at the hints and answer. Can you explain exactly why does change in direction conclude that the pattern will create a circle? In the interviews, such hints will not be given.
Don't you have Java solutions pls
Check in below comments.
@@Neethirajan85 where?
@@onepercentbetter3313 class Solution {
public boolean isRobotBounded(String instructions) {
int dirX = 0;
int dirY = 1;
int x=0;
int y=0;
for (char c : instructions.toCharArray()) {
if (c=='G') {
x = x + dirX;
y = y + dirY;
} else if (c=='L') {
int temp = dirX;
dirX = -1 * dirY;
dirY = temp;
} else {
int temp = dirX;
dirX = dirY;
dirY = -1 * temp;
}
}
return (x == 0 && y == 0) || (dirX != 0 || dirY != 1) ;
}
}
The solution using the inherent periodic nature by running the command string 4 times is cleaner and more intuitive.
And takes longer. And shows a lack of optimization skills. The hiring manager won't like that. They'll have to worry that every time you get a task, you might brute force with O(n^2) or O(n!) solutions because you feel it's more intuitive. Software engineers get paid to engineer.
Could u please solve 725. Split Linked List in Parts?
whats wrong in this c++ code:
bool isRobotBounded(string instructions) {
int dirX = 0, dirY = 1;
int x = 0, y = 0;
for(char ch: instructions){
if(ch == 'G'){
x = x + dirX;
y = y + dirY;
}
else if(ch == 'L'){
char temp = dirX;
dirX = -1 * dirY;
dirY = temp;
}
else{
char temp = dirX;
dirX = dirY;
dirY = -1 * temp;
}
}
return ((x == 0) && (y == 0)) || ((dirX != 0) && (dirY != 1));
}
It's so disheartening to see just 1 like in 20 hours ,I request all to please atleast leave a like , a like doesn't cost anything , but someone's efforts does .
Please someone clear my doubt that , in interview do we have to write the code from main function or only the function . Please @NeetCode or @ anyone
Most of the interviewer expects only the function.