Jobs

Interviews

Discussions

Path Crossing

#409 Most AskedEasy

Path Crossing #409 Most Asked

Easy

Adobe

6 views

Topics:

Strings

Given a string path, where path[i] = 'N', 'S', 'E' or 'W', each representing moving one unit north, south, east, or west, respectively. You start at the origin (0, 0) on a 2D plane and walk on the path specified by path.

Return true if the path crosses itself at any point, that is, if at any time you are on a location you have previously visited. Return false otherwise.

Example 1:

Input: path = "NES"
Output: false 
Explanation: Notice that the path doesn't cross any point more than once.

Example 2:

Input: path = "NESWW"
Output: true
Explanation: Notice that the path visits the origin twice.

Constraints:

1 <= path.length <= 10⁴
path[i] is either 'N', 'S', 'E', or 'W'.

Try coding it in LeetCode

Path Crossing

#409 Most AskedEasy

Path Crossing #409 Most Asked

Easy

Adobe

6 views

Topics:

Strings

Return true if the path crosses itself at any point, that is, if at any time you are on a location you have previously visited. Return false otherwise.

Example 1:

Input: path = "NES"
Output: false 
Explanation: Notice that the path doesn't cross any point more than once.

Example 2:

Input: path = "NESWW"
Output: true
Explanation: Notice that the path visits the origin twice.

Constraints:

1 <= path.length <= 10⁴
path[i] is either 'N', 'S', 'E', or 'W'.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range and data type of the characters in the path string?
Is an empty path string considered a crossing path, and what should the return value be in that case?
Is the starting point (0, 0) considered the first location in the path, and should the path be considered crossing if we return to the origin?
Should I assume the input string only contains the characters 'N', 'S', 'E', and 'W'?
If the path crosses itself multiple times, should I return `true` as soon as the first crossing is detected?

Brute Force Solution

Approach

The brute force approach to this problem involves simulating every possible path the traveler could take based on the given directions. We'll keep track of every place the traveler visits. If the traveler ever revisits a location, the path crosses itself.

Here's how the algorithm would work step-by-step:

Start with the traveler at the initial location (0, 0).
For each direction in the given sequence of directions, update the traveler's current location.
After moving, check if the traveler's new location has been visited before.
If the new location has been visited, the path crosses itself, and you're done.
If the new location hasn't been visited, add it to the list of visited locations and continue to the next direction.
If you go through all the directions and never revisit a location, the path does not cross itself.

Code Implementation

def path_crossing_brute_force(path):
    current_location_x = 0
    current_location_y = 0
    visited_locations = set()
    visited_locations.add((current_location_x, current_location_y))

    for direction in path:
        if direction == 'N':
            current_location_y += 1
        elif direction == 'S':
            current_location_y -= 1
        elif direction == 'E':
            current_location_x += 1
        else:
            current_location_x -= 1

        #Check if we have revisited this location
        if (current_location_x, current_location_y) in visited_locations:

            return True

        #Add current location to the visited set
        visited_locations.add((current_location_x, current_location_y))

    #If we never revisit return false
    return False

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the given directions string of length n. For each direction, it updates the current coordinates and checks if the new location has been visited before. The check for visited locations involves searching a data structure (e.g., a set or list) which takes, on average, O(1) time with a set or O(n) time in the worst case with a list if a linear search is used. Assuming an efficient data structure like a set is used for storing visited locations, the lookup operation takes O(1) on average. Therefore, the overall time complexity is dominated by the iteration through the directions string, resulting in O(n) time complexity, plus n * O(1) lookups in a set, which simplifies to O(n).

Space Complexity

O(N) – The algorithm maintains a data structure, likely a set or list, to store the visited locations. In the worst case, the traveler visits N distinct locations, where N is the number of directions in the input. Thus, the space required to store the visited locations grows linearly with the number of directions. Therefore, the auxiliary space complexity is O(N).

Optimal Solution

Approach

We need to figure out if a path ever crosses itself. We can do this by keeping track of every place the path has been. If the path ever revisits a place, then it has crossed itself.

Here's how the algorithm would work step-by-step:

Start at the beginning, which we can call the origin.
Keep a record of every place the path visits.
For each step of the path, calculate the new place it will be.
Before moving to the new place, check if that place is already in our record of places visited.
If the new place is already in the record, the path has crossed itself, and we're done.
If the new place is not in the record, add it to the record and continue to the next step of the path.
If we reach the end of the path without finding any repeated places, then the path has not crossed itself.

Code Implementation

def is_path_crossing(path): 
    x_coordinate = 0
    y_coordinate = 0
    visited_positions = set()
    visited_positions.add((0, 0))

    for move in path:
        if move == 'N':
            y_coordinate += 1
        elif move == 'S':
            y_coordinate -= 1
        elif move == 'E':
            x_coordinate += 1
        else:
            x_coordinate -= 1

        new_position = (x_coordinate, y_coordinate)

        # Check if the new position has already been visited.
        if new_position in visited_positions:
            return True

        # Add the new position to the set of visited positions.
        visited_positions.add(new_position)

    return False

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input path of length n once. In each iteration, it calculates the new coordinates and checks if those coordinates already exist in a set of visited coordinates. The set lookup operation (checking if coordinates exist) takes O(1) time on average. Therefore, the time complexity is dominated by the single iteration over the path of length n, resulting in O(n) time complexity.

Space Complexity

O(N) – The algorithm maintains a record of visited places. This record grows linearly with the number of steps in the path, which is determined by the input size N (the number of steps). In the worst-case scenario, where the path never crosses itself, the record will contain N distinct coordinates. Therefore, the auxiliary space used is proportional to the number of steps in the path, N, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input string	Return True immediately as the starting point is considered visited; no path is taken to cross itself.
String of length 1	Return False immediately as only one move is made and a crossing requires at least two moves.
Very long input string	The solution uses a set which has O(1) lookups for visited locations so performance remains acceptable even for long paths; memory usage scales linearly.
Path returns to origin immediately	The set of visited coordinates immediately detects the duplicate and returns True.
Path crosses itself far away from the origin	The set will eventually contain this coordinate again causing the algorithm to return True.
Path moves only in one direction	The algorithm correctly tracks the path and never returns True as no coordinate is ever revisited.
Integer overflow in coordinate calculations with very long paths	Consider using a larger integer type (e.g., long) or clamping the coordinates to prevent overflows, or scaling down coordinates to keep them within reasonable bounds.
Path attempts to revisit Integer.MAX_VALUE, Integer.MIN_VALUE coordinates.	The set handles arbitrarily large integer values in coordinates if memory allows, otherwise clamping or scaling as per the integer overflow edge case applies.

Null or empty input string

How to Handle:

Return True immediately as the starting point is considered visited; no path is taken to cross itself.

String of length 1

How to Handle:

Return False immediately as only one move is made and a crossing requires at least two moves.

Very long input string

How to Handle:

The solution uses a set which has O(1) lookups for visited locations so performance remains acceptable even for long paths; memory usage scales linearly.

Path returns to origin immediately

How to Handle:

The set of visited coordinates immediately detects the duplicate and returns True.

Path crosses itself far away from the origin

How to Handle:

The set will eventually contain this coordinate again causing the algorithm to return True.

Path moves only in one direction

How to Handle:

The algorithm correctly tracks the path and never returns True as no coordinate is ever revisited.

Integer overflow in coordinate calculations with very long paths

How to Handle:

Consider using a larger integer type (e.g., long) or clamping the coordinates to prevent overflows, or scaling down coordinates to keep them within reasonable bounds.

Path attempts to revisit Integer.MAX_VALUE, Integer.MIN_VALUE coordinates.

How to Handle:

The set handles arbitrarily large integer values in coordinates if memory allows, otherwise clamping or scaling as per the integer overflow edge case applies.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range and data type of the characters in the path string?
Is an empty path string considered a crossing path, and what should the return value be in that case?
Is the starting point (0, 0) considered the first location in the path, and should the path be considered crossing if we return to the origin?
Should I assume the input string only contains the characters 'N', 'S', 'E', and 'W'?
If the path crosses itself multiple times, should I return `true` as soon as the first crossing is detected?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the traveler at the initial location (0, 0).
For each direction in the given sequence of directions, update the traveler's current location.
After moving, check if the traveler's new location has been visited before.
If the new location has been visited, the path crosses itself, and you're done.
If the new location hasn't been visited, add it to the list of visited locations and continue to the next direction.
If you go through all the directions and never revisit a location, the path does not cross itself.

Code Implementation

def path_crossing_brute_force(path):
    current_location_x = 0
    current_location_y = 0
    visited_locations = set()
    visited_locations.add((current_location_x, current_location_y))

    for direction in path:
        if direction == 'N':
            current_location_y += 1
        elif direction == 'S':
            current_location_y -= 1
        elif direction == 'E':
            current_location_x += 1
        else:
            current_location_x -= 1

        #Check if we have revisited this location
        if (current_location_x, current_location_y) in visited_locations:

            return True

        #Add current location to the visited set
        visited_locations.add((current_location_x, current_location_y))

    #If we never revisit return false
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

We need to figure out if a path ever crosses itself. We can do this by keeping track of every place the path has been. If the path ever revisits a place, then it has crossed itself.

Here's how the algorithm would work step-by-step:

Start at the beginning, which we can call the origin.
Keep a record of every place the path visits.
For each step of the path, calculate the new place it will be.
Before moving to the new place, check if that place is already in our record of places visited.
If the new place is already in the record, the path has crossed itself, and we're done.
If the new place is not in the record, add it to the record and continue to the next step of the path.
If we reach the end of the path without finding any repeated places, then the path has not crossed itself.

Code Implementation

def is_path_crossing(path): 
    x_coordinate = 0
    y_coordinate = 0
    visited_positions = set()
    visited_positions.add((0, 0))

    for move in path:
        if move == 'N':
            y_coordinate += 1
        elif move == 'S':
            y_coordinate -= 1
        elif move == 'E':
            x_coordinate += 1
        else:
            x_coordinate -= 1

        new_position = (x_coordinate, y_coordinate)

        # Check if the new position has already been visited.
        if new_position in visited_positions:
            return True

        # Add the new position to the set of visited positions.
        visited_positions.add(new_position)

    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return True immediately as the starting point is considered visited; no path is taken to cross itself.
String of length 1	Return False immediately as only one move is made and a crossing requires at least two moves.
Very long input string	The solution uses a set which has O(1) lookups for visited locations so performance remains acceptable even for long paths; memory usage scales linearly.
Path returns to origin immediately	The set of visited coordinates immediately detects the duplicate and returns True.
Path crosses itself far away from the origin	The set will eventually contain this coordinate again causing the algorithm to return True.
Path moves only in one direction	The algorithm correctly tracks the path and never returns True as no coordinate is ever revisited.
Integer overflow in coordinate calculations with very long paths	Consider using a larger integer type (e.g., long) or clamping the coordinates to prevent overflows, or scaling down coordinates to keep them within reasonable bounds.
Path attempts to revisit Integer.MAX_VALUE, Integer.MIN_VALUE coordinates.	The set handles arbitrarily large integer values in coordinates if memory allows, otherwise clamping or scaling as per the integer overflow edge case applies.

Null or empty input string

How to Handle:

Return True immediately as the starting point is considered visited; no path is taken to cross itself.

String of length 1

How to Handle:

Return False immediately as only one move is made and a crossing requires at least two moves.

Very long input string

How to Handle:

The solution uses a set which has O(1) lookups for visited locations so performance remains acceptable even for long paths; memory usage scales linearly.

Path returns to origin immediately

How to Handle:

The set of visited coordinates immediately detects the duplicate and returns True.

Path crosses itself far away from the origin

How to Handle:

The set will eventually contain this coordinate again causing the algorithm to return True.

Path moves only in one direction

How to Handle:

The algorithm correctly tracks the path and never returns True as no coordinate is ever revisited.

Integer overflow in coordinate calculations with very long paths

How to Handle:

Consider using a larger integer type (e.g., long) or clamping the coordinates to prevent overflows, or scaling down coordinates to keep them within reasonable bounds.

Path attempts to revisit Integer.MAX_VALUE, Integer.MIN_VALUE coordinates.

How to Handle:

The set handles arbitrarily large integer values in coordinates if memory allows, otherwise clamping or scaling as per the integer overflow edge case applies.

0/469 Adobe questions completed

0/469 completed