easy Path Crossing

Problem Statement

You are given a string path, where path[i] = 'N', 'S', 'E' or 'W',, each representing the movement of one unit in North, South, East, and West direction, respectively. You start the journey on the 2D plane from origin (0, 0), and move towards the directions given in path string.

Return true, if your path crosses itself at any point, that is, if you ever visit the same point twice. Otherwise, return false.

Examples

• Example 1:

  • Input: "NESW"
  • Expected Output: true
  • Justification: The path moves north, east, south, and then west, returning to the origin. This forms a loop, crossing at the starting point.

• Example 2:

  • Input: "NNWWSS"
  • Expected Output: false
  • Justification: The path moves north twice, west twice, and south twice. It forms a rectangle and ends two units west of the origin without crossing any previous point.

• Example 3:

  • Input: "NESWWN"
  • Expected Output: true
  • Justification: The path moves north, east, south, west twice, and then north, crossing its own path on the second west move.

Solution

To solve this problem, we will use a set to keep track of all the points visited during the journey. The idea is to convert the movement instructions into coordinates on the grid, starting from the origin (0, 0). For each direction in the sequence, we'll update our current position and check if this new position has been visited before by consulting our set. If it has, we conclude the path crosses itself. If we finish processing all directions without revisiting any point, the path does not cross.

This approach works because it directly simulates the journey, making it straightforward to understand and implement. It's effective because checking for duplicates in a set is fast, ensuring our solution is efficient for paths with a large number of steps.

Step-by-step algorithm

• Initialize a set to store visited points, starting with the origin point (0, 0).
• Initialize variables to track the current position on the grid (x, y), starting from (0, 0).
• Iterate over each direction in the input sequence:
  • Update the current position (x, y) based on the direction:
    • N: decrement y
    • S: increment y
    • E: increment x
    • W: decrement x
  • Check if the new position (x, y) is already in the set of visited points.
    • If yes, return true indicating the path crosses itself.
    • Otherwise, add the new position to the set and continue.
• If the loop completes without finding any duplicate positions, return false.

Algorithm Walkthrough

Let's consider the input: "NESWWN"

• Initial Setup:
  • Visited Set: { "0,0" }
  • Current Position: (0, 0)

Iteration 1: Direction = 'N'

• Move North: (0, 0) to (0, -1)
• Visited Set: { "0,0", "0,-1" }
• Current Position: (0, -1)

Iteration 2: Direction = 'E'

• Move East: (0, -1) to (1, -1)
• Visited Set: { "0,0", "0,-1", "1,-1" }
• Current Position: (1, -1)

Iteration 3: Direction = 'S'

• Move South: (1, -1) to (1, 0)
• Visited Set: { "0,0", "0,-1", "1,-1", "1,0" }
• Current Position: (1, 0)

Iteration 4: Direction = 'W'

• Move West: (1, 0) to (0, 0)
• Here, (0, 0) is already in the set. So, return true.

Code

import java.util.HashSet;
import java.util.Set;

public class Solution {

  public boolean isPathCrossing(String path) {
    Set<String> visited = new HashSet<>(); // Use a HashSet to record visited coordinates
    int x = 0, y = 0; // Initialize starting point at the origin (0, 0)
    visited.add(x + "," + y); // Add the origin to the visited set

    for (char direction : path.toCharArray()) { // Loop through each character in the path string
      // Update coordinates based on the direction
      if (direction == 'N') y--;
      else if (direction == 'S') y++;
      else if (direction == 'E') x++;
      else if (direction == 'W') x--;

      String currentPos = x + "," + y; // Create a string representation of the current position
      if (visited.contains(currentPos)) return true; // If this position was already visited, path crosses
      visited.add(currentPos); // Otherwise, add the current position to the set of visited coordinates
    }

    return false; // If no crossing is detected, return false
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Test the algorithm with example inputs
    System.out.println(solution.isPathCrossing("NESW")); // Expected: true
    System.out.println(solution.isPathCrossing("NNWWSS")); // Expected: false
    System.out.println(solution.isPathCrossing("NESWWN")); // Expected: true
  }
}

Complexity Analysis

• Time Complexity: , where N is the length of the path string. We iterate through the string once, performing constant-time operations for each character.
• Space Complexity: , in the worst case, the path does not cross itself, and we visit N unique positions, storing each in the set.