Robot Bounded in Circle - Math & Geometry - Leetcode 1041 - Python

0:00 - Read the problem
1:59 - Drawing Explanation
9:34 - Coding Explanation

leetcode 1041

#amazon #coding #interview
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[jonaskhanwald]

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.

[ljdukemanster]

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.

[DanhWasHere]

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.

[linwingho]

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!

[MrPhilippos]

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.

[mailsiraj]

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.

[akshaychavan]

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

[irarose]

Thank you for all the solved problems and clear explanations :)

[jx]

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!

[anujapuranik]

Thankyou again for all your videos and amazing explanation. This is the easiest explanation I ever saw to this problem!!

[mostinho]

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

[susmi]

I swear, if I get a job, it will be only because of NeetCode's incredible explanation!

[tkoiop]

Was waiting for some time, thank you for all the effort you put in! Motivates a ton!

[mikemihay]

Thank you for the effort to make this videos!

[ahmadaskar]

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?

[mohdziaalkhair]

The rule for a rotation by 90° about the origin is (x, y)→(−y, x)

[infiniteloop]

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.

[brucebatmanwayne]

9:35 how did your application at freddie mac go? :p

[nikhildinesan]

Happy to see you back !!! was waiting for your videos....

[algorithmo]

Finally! Hope you are doing well and alright! :D