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
true
if 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
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.