Leetcode – Path Crossing Solution

Spread the love

The “Path Crossing” problem is an interesting programming challenge available on Leetcode. This problem comes under the category of array manipulation and string parsing, while also requiring knowledge of data structures such as sets. Although it may initially seem straightforward, the problem actually allows for the exploration of various programming concepts. In this comprehensive guide, we’ll break down the problem, consider different approaches to solving it, and explore time and space complexities.

Problem Statement

The problem requires you to find if a path crosses itself. Given a string path, where path[i] represents the direction (‘N’ for North, ‘E’ for East, ‘S’ for South, and ‘W’ for West), you start at the origin (0, 0) and walk in the given direction. The task is to determine whether the path crosses itself. In other words, whether you reach a point you have previously been to.

Example

Input: path = "NES"
Output: False
Explanation: The path goes North, then East, then South. It doesn't cross itself.

Naive Approach: Using List of Tuples

A simple way to solve this problem is by maintaining a list of tuples, each containing the coordinates you pass through. By checking whether the current coordinate is already in the list before adding it, you can determine whether the path crosses itself.

Python code:

def isPathCrossing(path):
    x, y = 0, 0
    visited = [(x, y)]

    for move in path:
        if move == 'N':
            y += 1
        elif move == 'S':
            y -= 1
        elif move == 'E':
            x += 1
        else:  # 'W'
            x -= 1

        if (x, y) in visited:
            return True
        visited.append((x, y))

    return False

# Test the function
print(isPathCrossing("NES"))  # Output should be False

Time Complexity

This approach has a time complexity of O(n^2) due to the use of the in operator with a list.

Space Complexity

The space complexity is O(n) as we store all visited points.

Optimized Approach: Using Set

To improve the efficiency of the algorithm, you can use a set to store visited coordinates. Lookup in a set is O(1) on average, which will make the algorithm faster.

Python Code:

def isPathCrossing(path):
    x, y = 0, 0
    visited = {(x, y)}

    for move in path:
        if move == 'N':
            y += 1
        elif move == 'S':
            y -= 1
        elif move == 'E':
            x += 1
        else:  # 'W'
            x -= 1

        if (x, y) in visited:
            return True
        visited.add((x, y))

    return False

# Test the function
print(isPathCrossing("NES"))  # Output should be False

Time Complexity

The time complexity is O(n) due to the use of a set.

Space Complexity

The space complexity remains O(n).

Edge Cases and Further Considerations

  • Empty Path: What happens when the path is an empty string? According to the problem, an empty path would not cross itself.
  • Single Direction: If the path contains only one type of direction, like “NNNN”, it won’t cross itself. This can be a quick check to exit the function early.
  • Circular Paths: Paths like “NESW” will result in crossing at the origin.

Conclusion

The “Path Crossing” problem is a great exercise in array manipulation, string parsing, and data structure selection. We’ve walked through naive and optimized approaches to solve it, evaluated their time and space complexities, and looked at edge cases.

Leave a Reply