Leetcode 1496: Path Crossing
You are given a string path where each character represents a movement direction (‘N’ for north, ‘S’ for south, ‘E’ for east, ‘W’ for west). Starting from the origin (0, 0), follow the path and check if you cross your own path at any point, meaning visiting a location more than once. Return true if the path crosses itself, and false otherwise.
Problem
Approach
Steps
Complexity
Input: The input is a string path consisting of 'N', 'S', 'E', and 'W', where each character represents a movement direction.
Example: path = "NEWS"
Constraints:
• 1 <= path.length <= 10^4
• path[i] is one of 'N', 'S', 'E', 'W'.
Output: Return true if the path crosses itself, meaning you visit a location you have already been to. Otherwise, return false.
Example: Output: false
Constraints:
• The path will contain at least one character.
Goal: The goal is to track the movements and check if any position is visited more than once using a set data structure.
Steps:
• Initialize a set to store visited coordinates.
• Iterate through the characters in the path, updating the current position based on the direction.
• If the current position has been visited before, return true.
• If the loop finishes without revisiting a position, return false.
Goal: The length of the path is between 1 and 10^4. The path consists of the characters 'N', 'S', 'E', and 'W'.
Steps:
• 1 <= path.length <= 10^4
• path[i] is either 'N', 'S', 'E', or 'W'.
Assumptions:
• The path consists of valid directions only.
• Input: path = "NEWS"
• Explanation: The path starts at the origin, moves north, then east, then west, and finally south, visiting no location twice, so it does not cross itself.
• Input: path = "NESWN"
• Explanation: After moving north, east, south, west, and then north again, the path revisits the origin, so it crosses itself.
Approach: We can efficiently determine if the path crosses by keeping track of each position we visit using a set. If we ever encounter a position that we have already visited, we know the path crosses.
Observations:
• A set is ideal for this problem since it allows constant time lookups to check if a location has been visited.
• By iterating over the path and updating our current position, we can easily check if any position has been revisited.
Steps:
• Initialize a set to keep track of visited positions.
• Set the initial position as (0, 0).
• For each character in the path, update the position based on the direction.
• After each move, check if the new position has been visited. If it has, return true.
• If the loop completes without revisiting any position, return false.
Empty Inputs:
• An empty input path is not valid since the constraints ensure at least one move.
Large Inputs:
• The solution must handle path lengths up to 10^4 efficiently.
Special Values:
• If the path moves in a complete loop, it will return true since the origin will be revisited.
Constraints:
• The solution must be efficient enough to handle paths with lengths up to 10^4.
bool isPathCrossing(string path) {
int x = 0,y=0;
set<pair<int,int>>s;
s.insert({0,0});
for(char p: path){
if(p == 'N') y++;
else if(p == 'S')y--;
else if(p == 'E') x++;
else x--;
if(s.find({x,y}) != s.end()) return true;
else s.insert({x,y});
}
return false;
}
1 : Function Declaration
bool isPathCrossing(string path) {
The function `isPathCrossing` takes a string `path` as input and returns a boolean indicating whether the path crosses itself.
2 : Variable Initialization
int x = 0, y = 0;
Initialize `x` and `y` to 0. These variables represent the current position along the path on a 2D grid, starting at the origin (0,0).
3 : Set Initialization
set<pair<int, int>> s;
Initialize a set `s` to store the visited coordinates as pairs of integers. This will help track previously visited positions.
4 : Set Insertion
s.insert({0, 0});
Insert the starting coordinate (0,0) into the set `s` as the initial position.
5 : Loop
for(char p: path){
Start a loop to iterate over each character in the `path` string. Each character represents a direction to move.
6 : Movement
if(p == 'N') y++;
If the character is 'N' (North), increment `y` to move one unit up along the y-axis.
7 : Movement
else if(p == 'S') y--;
If the character is 'S' (South), decrement `y` to move one unit down along the y-axis.
8 : Movement
else if(p == 'E') x++;
If the character is 'E' (East), increment `x` to move one unit to the right along the x-axis.
9 : Movement
else x--;
If the character is 'W' (West), decrement `x` to move one unit to the left along the x-axis.
10 : Position Check
if(s.find({x, y}) != s.end()) return true;
Check if the current position (x, y) has been visited before by searching the set `s`. If the position is found, it means the path crosses itself, so return `true`.
11 : Set Update
else s.insert({x, y});
If the current position has not been visited before, insert it into the set `s` to mark it as visited.
12 : Return Statement
return false;
If no crossing was detected after checking all directions in the path, return `false`.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the length of the path, since we only need to iterate over the path once and check each position in the set.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the storage required for the set of visited positions.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus