Intro: I am a former accountant turned software engineer graduated from coding bootcamp. Algorithms and Data Structure is an unavoidable part of interviews for most of the tech companies now. And one of my friends told me that you need to solve a medium leetcode problem under 60 seconds in order to get into the top tech companies.So I thought I'd start learning how to do it while job searching.
Since I have no clue on how to solve any of the problems (even the easy ones), I thought there is no point for me to waste hours and can't get it figured out. Here is my approach:
- Pick a leetcode problem randomly or Online Assessment from targeted companies.
- Study 1-2 solutions from Youtube or LeetCode discussion section. One brute force solution, another one more optimal.
- Write a blog post with detailed explanation and do a verbal walk through to help understand the solutions better.
- Code out the solution in LeetCode without looking at the solutions
- Combat the forgetting curve: Re-do the question for the next three days. And come back regularly to revisit the problem.
1041. Robot Bounded In Circle
Difficulty: Medium Language: JavaScript
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 theinstructionsgiven 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.
Constraints:
1 <= instructions.length <= 100instructions[i] is 'G', 'L' or, 'R'.
Solution:
Key so solving this problem is figure out how to change directions. Coordinates will be set up as x and y. And direction Up, Right, Down, Left is respectively set up as
[[0, 1], [1, 0], [0, -1], [-1, 0]]. Note these direction is located at index 0, 1, 2, 3 and these indices will be used in the next step to indicate which direction the robot should move towards. For example, when direction is at index 2, we get [0,-1] and that means the Robot will move down by 1 (y-1). How do we get these indices/directions? Since robot initially stands at (0, 0) and faces north, we will declare a variable 'head' as 0 facing north. If we turn right one time from head = 0, then we get 'head + 1'. That's index 1 -> [1,0] and Robot will move to the right by 1 (x+1). In order to turn left, we have to turn right three times from head = 0, then we get 'head + 3'. That's index 3 -> [-1,0] and Robot will move to the left by 1 (x-1).mod 4 is there because we come to face the same direction when you turn 4 times.
function isRobotBounded(instructions) {
const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];
//set up directions represent for 'Up', 'Right', 'Down', 'Left'
//respectively. We will later access these directions by their
//indices.
let head = 0;
//Since robot initially stands at (0, 0) and faces north, we will
//declare a variable 'head' as 0 facing north.
let x = 0;
let y = 0;
//Coordinates is set up as `x` and `y`.
for (const instruction of instructions) {
//Loop (note1) through each letter in the given string
if (instruction === 'G') {
x = x + dirs[head][0];
y = y + dirs[head][1];
//If (note 2) letter is 'G', update cordinate x and y based on the
//direction (note 3) obtained from steps below
} else if (instruction === 'L') {
head = (head + 3) % 4;
//if (note 2) letter is 'L', add 3 to 'head' then % 4 to turn
//left, see explanation above to see why we are adding 3 and % 4
} else {
head = (head + 1) % 4;
//if (note 2) letter is 'R', add 1 to 'head' then % 4 to turn
//right, see explanation above to see why we are adding 1 and % 4
}
}
const isAtOrigin = (x === 0 && y === 0);
const isHeadingNorth = head === 0
return isAtOrigin || (! isHeadingNorth);
//return true if x and y both (note 5) equals to 0 (note 4), as
//[0,0] means Robot is at it's origin.
};
Time and Space Complexity
- Time: O(N)
- Space: O(1)
References:
LeetCode Problem Link
LeetCode Discussion: pivacik
LeetCode Discussion: hbjORbj
Note 1: Loop and Iteration
Note 2: if...else
Note 3: Access array item by its index
Note 4: Strict equality (===)
Note 5: Logical AND (&&)
Blog Cover Image Credit
Top comments (0)