[Solution]Problem 45:Robot Bounded In Circle [Amazon]
Math and Logic beat all
Hello all,
As promised yesterday, we will now be sharing the answer to one of my favorite Leetcode questions ever. You will learn a lot. I wish more questions were similar to this.
This problem can be found as problem 1041. Robot Bounded In Circle on Leetcode.
Problem
On an infinite plane, a robot initially stands at (0, 0) and faces north. Note that:
The north direction is the positive direction of the y-axis.
The south direction is the negative direction of the y-axis.
The east direction is the positive direction of the x-axis.
The west direction is the negative direction of the x-axis.
The robot can receive one of three instructions:
"G": go straight 1 unit."L": turn 90 degrees to the left (i.e., anti-clockwise direction)."R": turn 90 degrees to the right (i.e., clockwise direction).
The robot performs the instructions given in order, and repeats them forever.
Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.
Example 1:
Input: instructions = "GGLLGG"
Output: true
Explanation: The robot is initially at (0, 0) facing the north direction.
"G": move one step. Position: (0, 1). Direction: North.
"G": move one step. Position: (0, 2). Direction: North.
"L": turn 90 degrees anti-clockwise. Position: (0, 2). Direction: West.
"L": turn 90 degrees anti-clockwise. Position: (0, 2). Direction: South.
"G": move one step. Position: (0, 1). Direction: South.
"G": move one step. Position: (0, 0). Direction: South.
Repeating the instructions, the robot goes into the cycle: (0, 0) --> (0, 1) --> (0, 2) --> (0, 1) --> (0, 0).
Based on that, we return true.
Example 2:
Input: instructions = "GG"
Output: false
Explanation: The robot is initially at (0, 0) facing the north direction.
"G": move one step. Position: (0, 1). Direction: North.
"G": move one step. Position: (0, 2). Direction: North.
Repeating the instructions, keeps advancing in the north direction and does not go into cycles.
Based on that, we return false.
Example 3:
Input: instructions = "GL"
Output: true
Explanation: The robot is initially at (0, 0) facing the north direction.
"G": move one step. Position: (0, 1). Direction: North.
"L": turn 90 degrees anti-clockwise. Position: (0, 1). Direction: West.
"G": move one step. Position: (-1, 1). Direction: West.
"L": turn 90 degrees anti-clockwise. Position: (-1, 1). Direction: South.
"G": move one step. Position: (-1, 0). Direction: South.
"L": turn 90 degrees anti-clockwise. Position: (-1, 0). Direction: East.
"G": move one step. Position: (0, 0). Direction: East.
"L": turn 90 degrees anti-clockwise. Position: (0, 0). Direction: North.
Repeating the instructions, the robot goes into the cycle: (0, 0) --> (0, 1) --> (-1, 1) --> (-1, 0) --> (0, 0).
Based on that, we return true.
You can test your solution here
[FREE SUBS]To buy the solution for this problem, use any of the following links. The price is 3 USD. Once you send the payment, message me on IG, LinkedIn, Twitter, or by Email:
Venmo: https://account.venmo.com/u/FNU-Devansh
Paypal: paypal.me/ISeeThings
Or you can sign up for a Free Trial Below. Since the reception has been great, I got a special offer for y’all. You can get this newsletter free for 2 months, just by using the button below-
Step 1: Reading the Question Deeply
A step that is criminally underrated by all, reading the question well is my go-to opener. It gives allows us to spot possible next steps, appreciate the nuances, and foresee possible hurdles. If nothing, it will help you ask the right clarifying questions. As I’ve stated many times, I recommend annotating any interesting points as you read.
In this question, there are a few important points to notice. First off, we start off at the origin, facing north. Secondly, we will only be able to move in one of the 4 cardinal directions, since our angle shifts can only be integer multiples of 90. Our robot can’t go in one of those fake directions like South-East. Lastly, let’s look at what we’re expected to do-
Return
trueif and only if there exists a circle in the plane such that the robot never leaves the circle.
Now here is where those of you that just want to watch the world burn can have fun. Say yes to your interviewer, refuse to elaborate, and leave (holding very strong eye contact). If you’re on a zoom call, minimize your screen and proceed with your day (don’t exit the meeting, just leave the interviewer hanging and confused). Since this question doesn’t mention that the circle can’t be infinite (the plane is unbounded), you will technically be correct.
To those of you that actually want a job, continue reading on. Going forward, let’s assume what they actually mean is that the circle has to have a finite area.
Step 2: Dealing with Infinite Instructions
Many people I know were thrown off by the part of the question that mentioned the fact that instructions will go on for infinity. They didn’t understand how they could judge since the instructions would keep repeating.
This is where a little math can be helpful. If you’ve studied functions the way we discussed, you would have come across an idea called periodicity. A periodic function is simply a function that returns the same value at regular intervals. Let’s take a simple example:
def periodic(x: int):
if(x%2==0):
return 5
return 3 That function will return 5 for every even number and 3 for every odd number. No matter what number we’re at adding/removing 2 will give the same value. Thus we say that the function has a period of 2.
Why is that relevant here? In a way, this too is a periodic function. The instructions repeat after set intervals (the length of the list). This means that if we analyze it like a periodic function, we will be able to solve it. Trust me, that’s easier than it sounds.
That’s cool but how do we apply that here? Go back to the question. We know that there are two things that are relevant. The location and the direction our bot is facing. When it comes to periodic functions, we typically analyze them by looking at their values over one period. Let’s do that here.
Step 3: Analyzing periodicity
Our analysis is helped by one thing. Helped a lot in fact. That is- we only care about the bot at the end of the period. The state of the bot at the end of one period will tell us what happens overall.
This is where we apply a staple of our problem-solving toolkit, the case-by-case analysis. Right off the bat, we know that there are two possibilities for our bot’s location at the end of the period-
Bot ends at origin- This clearly means that it will always stay bounded. This one is fairly obvious. But as a wise man (me) said, “no fruit better than the low hanging one”.
Bot is not at the origin- Let’s break it down further. Clearly now we want to look into the direction, and how that impacts the overall bot behavior.
This is where the next phase comes in. Let’s look at how directions impact where our bot ends up.
Step 4: The impact of Direction
The first clear impact of direction is starting while facing north. In this case, we know that we have moved some distance from the origin, and the bot is still facing in the same direction it started in. Like a real trooper, it will continue to march forward into the sunset.
If the location at the end of period= (x,y) [facing north]
then the location at the end of period 2= 2(x,y) [facing north]
and so on… Thus it will be unbounded. We return false in this case
When it comes to the South, this is reversed. Whatever progress is made away from the origin, will be eliminated now.
If the location at the end of period= (x,y) [facing south]
then the location at the end of period 2= 0,0 [facing north]
location at end of period 3= (x,y) [facing south]...
How about East? If the robot ends up facing east after iteration 1, it will be facing south after iteration 2, west after iteration 3, and north again after iteration 4. The distance it traveled in the north direction cancels that of the south, and the distance it traveled in the east direction cancels that of the west. So the robot is back to the origin after 4 iterations. Looking at our Math
If the location at the end of period= (x,y) [facing east]
then the location at the end of period 2= (x+y,y-x) [facing south]
location at end of period 3= (y,-x) [facing west]
location at end of period 4= (0,0) [facing north] #back to start
...
West will have the same result as east, just reversed. This covers all the directions. Thus we know that if our bot is at origin or NOT facing north, it will be bounded.
Now let’s cover the code.
Step 5: Coding it up
The first thing on your mind is how we encode direction. What does direction actually mean?
Simply put, the direction will tell you how your location will change when you move one unit distance. That simple. Since our location is based on our x,y coordinates, we must split the effect of our direction on x,y as well.
dX, dY =0,1 #since we start facing northYou will often see solutions use dX, dY for denoting the value of change in x and y respectively. This is because a change in math is represented by delta. This is also why calculus denotes slope as dx/dy (change in x divided by change in y). We will represent our directions with the same.
It should be clear that dX will tell us how many units we move right, and dY will tell us how many units we move forward.
How do each of our commands translate into calculations?
“G": go straight 1 unit- In this case, we’ll just go forward in whatever direction we are facing.
if d=='G':
x,y = x + dX,y +dY"L": turn 90 degrees to the left (i.e., anti-clockwise direction)- When we turn left, what was new forward is what used to be left previously. If we move that direction, then relative to the origin, we have moved left. We will move y units. Thus our new dx is -dy
elif d=='L':
dX,dY = -1*dY, dXSimilar logic applies to dy becoming dx.
"R": turn 90 degrees to the right (i.e., clockwise direction)- This is the inverse of the first case.
dX,dY = dY ,-1*dXTake a second to look at to look at it yourself if you’re not convinced. I sketched out a few small cases on paper. Our math analysis earlier will be helpful here.
Let’s put everything together
class Solution:
def isRobotBounded(self, instructions: str) -> bool:
dX, dY =0,1
x,y =0,0
for d in instructions:
if d=='G':
x,y = x + dX,y +dY
elif d=='L':
dX,dY = -1*dY, dX
else:
dX,dY = dY ,-1*dX
return (x,y) == (0,0) or (dX, dY) !=(0,1)
Time Complexity- O(N). We can’t get any better than this because we must go through the instructions at least once.
Space Complexity- O(1)
Make sure you share your thoughts on this question/solution/any interesting questions/developments in the comments or through my links.
Stay Woke. I’ll see you living the dream.
Go kill all,
Devansh <3
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75