Thanks, for that easy explanation 🙂. Currently i am beginner , i was struct in this problem near mapping and stack but you cleared it very well . Again thanks for the explanation🙏🏻☺
Could you first explain the problem before giving the solution? That's what you usually do, and today I feel like I missed out on a problem I could have solved myself.
Sir, I would recommend to use either Pseudo Code, or simpler Python( and not one liners or Python for coding interviews) as I think many viewers could be using other languages like Java, C++, etc. Introducing one liners will kind of make our experience less good.
I agree, but the one liners in this case are pretty trivial to translate to other languages. Since it's a leetcode hard, I'm pretty sure most viewers of this one would be able to write a loop to add elements to a map or list. There's a lot of value in having less verbose code. I don't wanna hold the python viewers back just because some people still use java (no offense to the java people)
@@NeetCodeIO Thanks for replying sir. These much one liners are okay, but please don't go further in this direction, where trouble starts to arise for other language users. I have no hate for Python, I just prefer strongly typed languages. I really appreciate your videos, and I am following you for a long time. Thank you for your amazing explanations😃.
My solution (code below), using the similar stack approach has the same TC ( O(nlogn) ) and SC ( O(N) ) but it TLE'd (Test Cases 2430 / 2433 passed). Do you think this will be accepted as a good solution in interview. ``` class Solution: def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]: robots = sorted([list(x) for x in zip(positions, directions, healths)]) stack = [] for robot in robots: skip = False while stack and stack[-1][1] == 'R' and robot[1] == 'L': if stack[-1][2] > robot[2]: stack[-1][2] -= 1 skip = True break elif stack[-1][2] < robot[2]: stack.pop() robot[2] -= 1 elif stack[-1][2] == robot[2]: stack.pop() skip = True break if not skip: stack.append(robot) stack = sorted(stack, key=lambda x: positions.index(x[0])) return [x[2] for x in stack] ```
It still is not appropriate and doesnot pass this test case: Input positions = [1,40] healths = [10,11] directions = "RL" Use Testcase Output [] Expected [10]
@@musickilely sure 1) make 2 lists, right and left robots and sort according to positions 2) now, for every left robot, search a robot closest to it and moving in right direction, we do this using binary search, returning floor (position of robot moving right) of the target(position of robot moving left) 3) then, we check the health and remove the robots from list or decrease health according to the condition 4) at the end, put all the remaining robots in the hashmap 5) and use hashmap to return list of remaining robots relative to their positions in input positions array here's the code for reference ``` class Solution { public List survivedRobotsHealths(int[] positions, int[] healths, String directions) { int n = directions.length(); ArrayList right = new ArrayList(); ArrayList left = new ArrayList(); for (int i = 0; i < n; i++) { char ch = directions.charAt(i); if (ch == 'R') { right.add(new int[] {positions[i], healths[i]}); } else { left.add(new int[] {positions[i], healths[i]}); } } right.sort((a, b) -> a[0] - b[0]); left.sort((a, b) -> a[0] - b[0]); // be at left idx // find floor of robots in right direction using bs // if right health < left health, remove right, and decrease left health, repeat process // if right health = left health, remove right, move left idx, repeat process // if right health > left health, move left idx, decrease right health, repeat process // at the end either right or left, any one will become empty, that is when you will have remaining robot in other list int leftIdx = 0; while (leftIdx < left.size() && !right.isEmpty()) { int[] left_robot = left.get(leftIdx); int left_pos = left_robot[0]; int left_health = left_robot[1]; int floor = floorBS(right, left_pos); if (floor == -1) { leftIdx++; continue; } int[] right_robot = right.get(floor); if (right_robot[1] < left_health) { // remove right right.remove(floor); // decrease left health left_robot[1] = left_health - 1; } else if (right_robot[1] == left_health) { // remove right right.remove(floor); // left_idx++ // leftIdx++; left.remove(leftIdx); } else { // right robot health > left robot health // decrease right health right_robot[1] = right_robot[1] - 1; // left_idx++ // leftIdx++; left.remove(leftIdx); } } return answer(positions, healths, left, right); } // return list as per positions static List answer(int[] positions, int[] healths, List left, List right) { HashMap map = new HashMap(); List ans = new ArrayList(); for (int[] robot : left) { map.put(robot[0], robot[1]); } for (int[] robot : right) { map.put(robot[0], robot[1]); } for (int position : positions) { if (map.containsKey(position)) { ans.add(map.get(position)); } } return ans; } static int floorBS(ArrayList list, int target) { int s = 0; int e = list.size() - 1; int ans = -1; while (s target) { e = m - 1; } else { return m; } } return ans; } } ```
@@musickilely sure 1) make 2 lists, right and left robots and sort according to positions 2) now, for every left robot, search a robot closest to it and moving in right direction, we do this using binary search, returning floor (position of robot moving right) of the target(position of robot moving left) 3) then, we check the health and remove the robots from list or decrease health according to the condition 4) at the end, put all the remaining robots in the hashmap 5) and use hashmap to return list of remaining robots relative to their positions in input positions array code for reference: ``` class Solution { public List survivedRobotsHealths(int[] positions, int[] healths, String directions) { int n = directions.length(); ArrayList right = new ArrayList(); ArrayList left = new ArrayList(); for (int i = 0; i < n; i++) { char ch = directions.charAt(i); if (ch == 'R') { right.add(new int[] {positions[i], healths[i]}); } else { left.add(new int[] {positions[i], healths[i]}); } } right.sort((a, b) -> a[0] - b[0]); left.sort((a, b) -> a[0] - b[0]); // be at left idx // find floor of robots in right direction using bs // if right health < left health, remove right, and decrease left health, repeat process // if right health = left health, remove right, move left idx, repeat process // if right health > left health, move left idx, decrease right health, repeat process // at the end either right or left, any one will become empty, that is when you will have remaining robot in other list int leftIdx = 0; while (leftIdx < left.size() && !right.isEmpty()) { int[] left_robot = left.get(leftIdx); int left_pos = left_robot[0]; int left_health = left_robot[1]; int floor = floorBS(right, left_pos); if (floor == -1) { leftIdx++; continue; } int[] right_robot = right.get(floor); if (right_robot[1] < left_health) { // remove right right.remove(floor); // decrease left health left_robot[1] = left_health - 1; } else if (right_robot[1] == left_health) { // remove right right.remove(floor); // left_idx++ // leftIdx++; left.remove(leftIdx); } else { // right robot health > left robot health // decrease right health right_robot[1] = right_robot[1] - 1; // left_idx++ // leftIdx++; left.remove(leftIdx); } } return answer(positions, healths, left, right); } // return list as per positions static List answer(int[] positions, int[] healths, List left, List right) { HashMap map = new HashMap(); List ans = new ArrayList(); for (int[] robot : left) { map.put(robot[0], robot[1]); } for (int[] robot : right) { map.put(robot[0], robot[1]); } for (int position : positions) { if (map.containsKey(position)) { ans.add(map.get(position)); } } return ans; } static int floorBS(ArrayList list, int target) { int s = 0; int e = list.size() - 1; int ans = -1; while (s target) { e = m - 1; } else { return m; } } return ans; } } ```
Can anyone guide me where I'm making mistake and my answer is not printing out properly class Solution { public: vector survivedRobotsHealths(vector& positions, vector& healths, string directions) { unordered_mapmp; int n = positions.size(); for(int i=0; i
Wohoo, Today i solved the problem myself
It is a great achivement for me 😁
May god bless you bro making amazing videos for free
This was the first hard problem I was able to solve by myself completely feels great😄
dayum bro so proud of you
Thanks, for that easy explanation 🙂. Currently i am beginner , i was struct in this problem near mapping and stack but you cleared it very well .
Again thanks for the explanation🙏🏻☺
This is master piece. How to make contrite problem lucid to follow.
@3:21 bro understands robot🤖🤖 now
Great explanation as always. Thank you
Isn't this kind of Asteroid collision problem?
awsome bro
Thanks for great intuition
3:18 robot living its best life.
indices = list(range(n))
indices.sort(key=lambda x: positions[x])
is another way to keep track of indices without the dictionary work
Thanks Sir to make this video..
Should probably be a medium, not even a hard medium
its all about understand the question i guess solution is quite easy to imagine
Amazing video @neetcode
Can please make a video on cat and mouse leetcode problem
Could you first explain the problem before giving the solution?
That's what you usually do, and today I feel like I missed out on a problem I could have solved myself.
Solved it!
this is exact same as astroid collision
That's what I thought too
Naitaji kujiunga ❤❤❤❤
imagine if this question involved speed gg
that would have been a nightmare
Like how much?@@SkySentry7
@@saibunny1253 how much what?
can we do this without sorting?
Na bro then it will give special error for some edge cases
it is possible, but you cannot use stack then. you'll have to use binary search, which will result in the same complexity.
Sir, I would recommend to use either Pseudo Code, or simpler Python( and not one liners or Python for coding interviews) as I think many viewers could be using other languages like Java, C++, etc. Introducing one liners will kind of make our experience less good.
I agree, but the one liners in this case are pretty trivial to translate to other languages. Since it's a leetcode hard, I'm pretty sure most viewers of this one would be able to write a loop to add elements to a map or list.
There's a lot of value in having less verbose code. I don't wanna hold the python viewers back just because some people still use java (no offense to the java people)
@@NeetCodeIO Thanks for replying sir. These much one liners are okay, but please don't go further in this direction, where trouble starts to arise for other language users. I have no hate for Python, I just prefer strongly typed languages.
I really appreciate your videos, and I am following you for a long time. Thank you for your amazing explanations😃.
My solution (code below), using the similar stack approach has the same TC ( O(nlogn) ) and SC ( O(N) ) but it TLE'd (Test Cases 2430 / 2433 passed). Do you think this will be accepted as a good solution in interview.
```
class Solution:
def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:
robots = sorted([list(x) for x in zip(positions, directions, healths)])
stack = []
for robot in robots:
skip = False
while stack and stack[-1][1] == 'R' and robot[1] == 'L':
if stack[-1][2] > robot[2]:
stack[-1][2] -= 1
skip = True
break
elif stack[-1][2] < robot[2]:
stack.pop()
robot[2] -= 1
elif stack[-1][2] == robot[2]:
stack.pop()
skip = True
break
if not skip:
stack.append(robot)
stack = sorted(stack, key=lambda x: positions.index(x[0]))
return [x[2] for x in stack]
```
Did you use chatgpt here? 🤔
I think tuple sorting is taking extra time here
@@SubhamKumar-eg1pw No ChatGPT
I'm first to comment,
Give this guy a medal lol
It still is not appropriate and doesnot pass this test case:
Input
positions =
[1,40]
healths =
[10,11]
directions =
"RL"
Use Testcase
Output
[]
Expected
[10]
I mean my code passed in the video. Is it possible you have a typo somewhere?
i solved it without using stack
(used binary search 💀)
took 432ms (beats 10%) lmao
can you share how ?
@@musickilely sure
1) make 2 lists, right and left robots and sort according to positions
2) now, for every left robot, search a robot closest to it and moving in right direction, we do this using binary search, returning floor (position of robot moving right) of the target(position of robot moving left)
3) then, we check the health and remove the robots from list or decrease health according to the condition
4) at the end, put all the remaining robots in the hashmap
5) and use hashmap to return list of remaining robots relative to their positions in input positions array
here's the code for reference
```
class Solution {
public List survivedRobotsHealths(int[] positions, int[] healths, String directions) {
int n = directions.length();
ArrayList right = new ArrayList();
ArrayList left = new ArrayList();
for (int i = 0; i < n; i++) {
char ch = directions.charAt(i);
if (ch == 'R') {
right.add(new int[] {positions[i], healths[i]});
} else {
left.add(new int[] {positions[i], healths[i]});
}
}
right.sort((a, b) -> a[0] - b[0]);
left.sort((a, b) -> a[0] - b[0]);
// be at left idx
// find floor of robots in right direction using bs
// if right health < left health, remove right, and decrease left health, repeat process
// if right health = left health, remove right, move left idx, repeat process
// if right health > left health, move left idx, decrease right health, repeat process
// at the end either right or left, any one will become empty, that is when you will have remaining robot in other list
int leftIdx = 0;
while (leftIdx < left.size() && !right.isEmpty()) {
int[] left_robot = left.get(leftIdx);
int left_pos = left_robot[0];
int left_health = left_robot[1];
int floor = floorBS(right, left_pos);
if (floor == -1) {
leftIdx++;
continue;
}
int[] right_robot = right.get(floor);
if (right_robot[1] < left_health) {
// remove right
right.remove(floor);
// decrease left health
left_robot[1] = left_health - 1;
} else if (right_robot[1] == left_health) {
// remove right
right.remove(floor);
// left_idx++
// leftIdx++;
left.remove(leftIdx);
} else {
// right robot health > left robot health
// decrease right health
right_robot[1] = right_robot[1] - 1;
// left_idx++
// leftIdx++;
left.remove(leftIdx);
}
}
return answer(positions, healths, left, right);
}
// return list as per positions
static List answer(int[] positions, int[] healths, List left, List right) {
HashMap map = new HashMap();
List ans = new ArrayList();
for (int[] robot : left) {
map.put(robot[0], robot[1]);
}
for (int[] robot : right) {
map.put(robot[0], robot[1]);
}
for (int position : positions) {
if (map.containsKey(position)) {
ans.add(map.get(position));
}
}
return ans;
}
static int floorBS(ArrayList list, int target) {
int s = 0;
int e = list.size() - 1;
int ans = -1;
while (s target) {
e = m - 1;
} else {
return m;
}
}
return ans;
}
}
```
How bro
@@musickilely sure
1) make 2 lists, right and left robots and sort according to positions
2) now, for every left robot, search a robot closest to it and moving in right direction, we do this using binary search, returning floor (position of robot moving right) of the target(position of robot moving left)
3) then, we check the health and remove the robots from list or decrease health according to the condition
4) at the end, put all the remaining robots in the hashmap
5) and use hashmap to return list of remaining robots relative to their positions in input positions array
code for reference:
```
class Solution {
public List survivedRobotsHealths(int[] positions, int[] healths, String directions) {
int n = directions.length();
ArrayList right = new ArrayList();
ArrayList left = new ArrayList();
for (int i = 0; i < n; i++) {
char ch = directions.charAt(i);
if (ch == 'R') {
right.add(new int[] {positions[i], healths[i]});
} else {
left.add(new int[] {positions[i], healths[i]});
}
}
right.sort((a, b) -> a[0] - b[0]);
left.sort((a, b) -> a[0] - b[0]);
// be at left idx
// find floor of robots in right direction using bs
// if right health < left health, remove right, and decrease left health, repeat process
// if right health = left health, remove right, move left idx, repeat process
// if right health > left health, move left idx, decrease right health, repeat process
// at the end either right or left, any one will become empty, that is when you will have remaining robot in other list
int leftIdx = 0;
while (leftIdx < left.size() && !right.isEmpty()) {
int[] left_robot = left.get(leftIdx);
int left_pos = left_robot[0];
int left_health = left_robot[1];
int floor = floorBS(right, left_pos);
if (floor == -1) {
leftIdx++;
continue;
}
int[] right_robot = right.get(floor);
if (right_robot[1] < left_health) {
// remove right
right.remove(floor);
// decrease left health
left_robot[1] = left_health - 1;
} else if (right_robot[1] == left_health) {
// remove right
right.remove(floor);
// left_idx++
// leftIdx++;
left.remove(leftIdx);
} else {
// right robot health > left robot health
// decrease right health
right_robot[1] = right_robot[1] - 1;
// left_idx++
// leftIdx++;
left.remove(leftIdx);
}
}
return answer(positions, healths, left, right);
}
// return list as per positions
static List answer(int[] positions, int[] healths, List left, List right) {
HashMap map = new HashMap();
List ans = new ArrayList();
for (int[] robot : left) {
map.put(robot[0], robot[1]);
}
for (int[] robot : right) {
map.put(robot[0], robot[1]);
}
for (int position : positions) {
if (map.containsKey(position)) {
ans.add(map.get(position));
}
}
return ans;
}
static int floorBS(ArrayList list, int target) {
int s = 0;
int e = list.size() - 1;
int ans = -1;
while (s target) {
e = m - 1;
} else {
return m;
}
}
return ans;
}
}
```
why is the code not working, some one help me
Have you thought about doing Tutorial Videos with your camera on? I think the videos will be so much better like that
Nah. Extra space
Or GTA clips covering half the screen?
I feel like seeing one's face and body language while teaching would helpful but I guess that's just me
@@datchkh you should hire a tutor then.
@@zweitekonto9654 🤓🤓🤓🤓🤓🤓
Can anyone guide me where I'm making mistake and my answer is not printing out properly
class Solution {
public:
vector survivedRobotsHealths(vector& positions, vector& healths, string directions) {
unordered_mapmp;
int n = positions.size();
for(int i=0; i