Path Crossing - Leetcode 1496 - Python
Key Takeaways
The video solves the Leetcode 1496 Path Crossing problem using a hash set to keep track of visited coordinates, with a time complexity of O(n) and memory complexity of O(n).
Full Transcript
hey everyone welcome back and let's write some more neat code today so today let's solve the problem path Crossing we're given a string path well first of all we start at the origin think of it as a 2d grid where maybe we have an X axis and a y AIS now in the path itself we're basically going to be given the directions that we are going to be moving so the directions are given to us with four characters north south east and west north is going to move us up by one so think of it as incrementing the Y value but leaving the x value the same we could even think of it as mapping to the Delta like the difference in X and the difference in y how would we represent that for n well thinking of it in terms of a pair of values like I said the x value stays the same so that's going to be a zero the yv value though is going to be incremented by one so we could think of North as being this Direction that's the direction we're moving in in now this is obviously a better way of thinking about it because we're dealing with numbers on a coordinate plane the character n does not really do anything for us let's not even think of it in end let's focus on this specific mapping you could do the same thing for all of these other characters South is obviously the opposite direction of this x is going to stay the same but Y is going to go in the opposite direction so I put a negative one here same thing for East and West except East is going to move us to the right by one so this is where the x value does change X will be incremented by one that's why I'm putting a positive one here y does not change West is the opposite direction so we change that to a negative 1 and keep y the same now we know how to actually interpret the path that we're given for example the path might be this nees this is how it's going to be given to us but we don't care about the individual characters we know n maps to this e maps to this s maps to this so starting at this position we can follow each of these coordinates and we'll know we move up one then we move to the right by one then we move down by one so this will allow us to actually update our coordinate it would be 01 here it would be 1 one here and it would be 1 Z here now given this path what exactly do we care about well the only thing is we want to know if we ever visit the same position twice now in this path clearly we don't of these four positions is distinct in that case we return false but if we ever did reach the same position twice for example from here what if the next character in the sequence was a w that would mean we move west here that would mean we end up at this coordinate a second time so in that case we return true because we do visit the same point multiple times so that's all we're trying to answer given this path and given this starting coordinate now how exactly do you think we can no if we do visit the same position twice probably the easiest way is to keep track of all the positions that we visited but what data structure should we use should we put it in an array probably not because looking up values in an array is not super efficient a better data structure would be something called a hash set which usually allows the lookup to be really efficient it's a constant time lookup so in that hash set we're going to store every single coordinate that we've already visited so that every time we visit a new coordinate we can immediately check if we visited it before if we have we will immediately return true otherwise we will continue with the path until we have gone through the entire path so with this the time complexity is going to be Big O of n because in the worst case we're going to have to go through the entire path let's assume the length of that is going to be n in terms of memory complexity we might have to have every single coordinate in the hash set and if every coordinate is unique then the memory complexity is also going to be Big O of n that's all we need to know now let's code this up we know a couple things we know we're going to keep track of visited cells in a hash set and to this we're going to add the pairs of coordinates well just the coordinates themselves and we know that the starting point is 0 0 so X is0 and Y is z now when we go through every character in this path we have a couple of choices what we could do one is we could have four if statements one for each possible character if it's n we know that X is going to stay the same but Y is going to be incremented by one so we could do something like this and we could do that for all four cases but a slightly better thing to do is actually like I said have a mapping we know that n is going to map to this Delta zero and One X stays the same but Y is incremented by one we know that South is going to be kind of the opposite X does stay the same but Y is going to be decremented by one we'll also fill it in for e and that is moving to the right and West is moving to the left so we just take the opposite of above NE - 1 and zero and the reason why we create this mapping I know this just because I've seen this type of trick before we create this mapping because now we don't need four conditions in this Loop what we can say now is whatever that character is let's use it as the key of the hashmap we declared up above and this will give us the DX dy I was talking about this will give us the Delta and now to determine the new location all we have to do is say X and Y are equal to X+ DX and y + Dy before I finish up the rest of this part I want to mention that we started at this coordinate so one thing I could do is just initialize the hashset like this to make sure that we already know that that's visited alternatively though I could also do it this way every time we enter this for Loop I'm going to say that this XY coordinate is now going to be marked visited so I could say like this visit. add this XY pair and I think with hash sets we have to add it like this rather than like as an array because I think two PS are immutable and that is a requirement to be the key of a hash set okay we've handled that so whenever we enter this we're going to Mark XY as visited but now we have the new coordinate the new XY and before we go to the next iteration of the loop we should probably check is this already visited is this new XY coordinate already in the visit hash set if it is then we clearly have visited the same position twice we have crossed a path so here we are told to return true now this Loop will pretty much run through the entire path until either it returns here or we reach the end of the loop if we reach the end of the loop that means we clearly did not cross paths and out here we can return false this is the entire code let's run it to make sure that it works and as you can see on the left yes it does and it's pretty efficient if you found this helpful please like And subscribe if you're preparing for coding interviews check out NE code. thanks for watching and I'll see you soon
Original Description
🚀 https://neetcode.io/ - A better way to prepare for Coding Interviews
🧑💼 LinkedIn: https://www.linkedin.com/in/navdeep-singh-3aaa14161/
🥷 Discord: https://discord.gg/ddjKRXPqtk
🐦 Twitter: https://twitter.com/neetcode1
🐮 Support the channel: https://www.patreon.com/NEETcode
⭐ BLIND-75 PLAYLIST: https://www.youtube.com/watch?v=KLlXCFG5TnA&list=PLot-Xpze53ldVwtstag2TL4HQhAnC8ATf
💡 DYNAMIC PROGRAMMING PLAYLIST: https://www.youtube.com/watch?v=73r3KWiEvyk&list=PLot-Xpze53lcvx_tjrr_m2lgD2NsRHlNO&index=1
Problem Link: https://leetcode.com/problems/path-crossing/
0:00 - Read the problem
0:16 - Drawing Explanation
4:10 - Coding Explanation
leetcode 1496
#neetcode #leetcode #python
Watch on YouTube ↗
(saves to browser)
Sign in to unlock AI tutor explanation · ⚡30
Playlist
Uploads from NeetCodeIO · NeetCodeIO · 0 of 60
← Previous
Next →
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
Leetcode 149 - Maximum Points on a Line - Python
NeetCodeIO
Design Linked List - Leetcode 707 - Python
NeetCodeIO
Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python
NeetCodeIO
Design Browser History - Leetcode 1472 - Python
NeetCodeIO
Number of Good Paths - Leetcode 2421 - Python
NeetCodeIO
Flip String to Monotone Increasing - Leetcode 926 - Python
NeetCodeIO
Maximum Sum Circular Subarray - Leetcode 918 - Python
NeetCodeIO
Find Closest Node to Given Two Nodes - Leetcode 2359 - Python
NeetCodeIO
Concatenated Words - Leetcode 472 - Python
NeetCodeIO
Data Stream as Disjoint Intervals - Leetcode 352 - Python
NeetCodeIO
LFU Cache - Leetcode 460 - Python
NeetCodeIO
N-th Tribonacci Number - Leetcode 1137
NeetCodeIO
Best Team with no Conflicts - Leetcode 1626 - Python
NeetCodeIO
Greatest Common Divisor of Strings - Leetcode 1071 - Python
NeetCodeIO
Shortest Path in a Binary Matrix - Leetcode 1091 - Python
NeetCodeIO
Insert into a Binary Search Tree - Leetcode 701 - Python
NeetCodeIO
Delete Node in a BST - Leetcode 450 - Python
NeetCodeIO
Shuffle the Array (Constant Space) - Leetcode 1470 - Python
NeetCodeIO
Fruits into Basket - Leetcode 904 - Python
NeetCodeIO
Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python
NeetCodeIO
Naming a Company - Leetcode 2306 - Python
NeetCodeIO
As Far from Land as Possible - Leetcode 1162 - Python
NeetCodeIO
Shortest Path with Alternating Colors - Leetcode 1129 - Python
NeetCodeIO
Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python
NeetCodeIO
Count Odd Numbers in an Interval Range - Leetcode 1523 - Python
NeetCodeIO
Contains Duplicate II - Leetcode 219 - Python
NeetCodeIO
Path with Maximum Probability - Leetcode 1514 - Python
NeetCodeIO
Add to Array-Form of Integer - Leetcode 989 - Python
NeetCodeIO
Unique Paths II - Leetcode 63 - Python
NeetCodeIO
Minimum Distance between BST Nodes - Leetcode 783 - Python
NeetCodeIO
Design Hashmap - Leetcode 706 - Python
NeetCodeIO
Range Sum Query Immutable - Leetcode 303 - Python
NeetCodeIO
Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
NeetCodeIO
Middle of the Linked List - Leetcode 876 - Python
NeetCodeIO
Course Schedule IV - Leetcode 1462 - Python
NeetCodeIO
Single Element in a Sorted Array - Leetcode 540 - Python
NeetCodeIO
Capacity to Ship Packages - Leetcode 1011 - Python
NeetCodeIO
IPO - Leetcode 502 - Python
NeetCodeIO
Minimize Deviation in Array - Leetcode 1675 - Python
NeetCodeIO
Longest Turbulent Array - Leetcode 978 - Python
NeetCodeIO
Last Stone Weight II - Leetcode 1049 - Python
NeetCodeIO
Construct Quad Tree - Leetcode 427 - Python
NeetCodeIO
Find Duplicate Subtrees - Leetcode 652 - Python
NeetCodeIO
Sort an Array - Leetcode 912 - Python
NeetCodeIO
Ones and Zeroes - Leetcode 474 - Python
NeetCodeIO
Remove Duplicates from Sorted Array II - Leetcode 80 - Python
NeetCodeIO
Maximum Twin Sum of a Linked List - Leetcode 2130 - Python
NeetCodeIO
Concatenation of Array - Leetcode 1929 - Python
NeetCodeIO
Symmetric Tree - Leetcode 101 - Python
NeetCodeIO
Check Completeness of a Binary Tree - Leetcode 958 - Python
NeetCodeIO
Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python
NeetCodeIO
Find Peak Element - Leetcode 162 - Python
NeetCodeIO
Accounts Merge - Leetcode 721 - Python
NeetCodeIO
Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python
NeetCodeIO
Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python
NeetCodeIO
Number of Zero-Filled Subarrays - Leetcode 2348 - Python
NeetCodeIO
Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python
NeetCodeIO
Sqrt(x) - Leetcode 69 - Python
NeetCodeIO
Successful Pairs of Spells and Potions - Leetcode 2300 - Python
NeetCodeIO
Optimal Partition of String - Leetcode 2405 - Python
NeetCodeIO
More on: Algorithm Basics
View skill →
Related AI Lessons
⚡
⚡
⚡
⚡
Bloom Filters, Explained Properly
Dev.to · Daksh Gargas
Prefix Sums: The Preprocessing Trick That Makes Range Queries Instant
Medium · Programming
I Thought I Was Ready for the Interview — Then One Simple Math Question Destroyed Me
Medium · Programming
Week 2(Day 10): LeetCode Two Pointers(slow & fast): Remove Duplicates from Sorted Array (Brute…
Medium · Python
Chapters (3)
Read the problem
0:16
Drawing Explanation
4:10
Coding Explanation
🎓
Tutor Explanation
DeepCamp AI