algoadvance

Leetcode 1496. Path Crossing

Problem Statement:

You are given a string path that describes the movement of a person on a 2D grid. Each character in the string represents a move:

The person starts at the origin (0, 0) on the grid. Return true if the path crosses itself at any point, that is, if the person visits a grid point more than once and false otherwise.

Clarifying Questions:

  1. Q: What should be returned if the path is empty?
    • A: Since there would be no movement, the output should be false.
  2. Q: Can the path contain invalid characters?
    • A: Based on the problem statement, it’s assumed that the path consists only of valid characters{‘N’, ‘S’, ‘E’, ‘W’}.
  3. Q: Are we given any constraints on the length of the path?
    • A: Typical constraints in coding interview problems would expect us to handle up to 10^5 characters efficiently. However, if not explicitly stated otherwise, let’s assume a reasonable upper limit like 10^4 for the sake of our solution.

Strategy:

  1. Coordinate System: Use a pair of coordinates (x, y) to track the current position on the grid.
  2. Track Visited Points: Use a HashSet to store positions that have been visited.
  3. Movement Updates: Based on each character in the path:
    • ‘N’: move north (y + 1),
    • ‘S’: move south (y - 1),
    • ‘E’: move east (x + 1),
    • ‘W’: move west (x - 1).
  4. Check for Revisit: After updating the coordinates for each move, check if the new position is already in the HashSet. If it is, return true. If not, add the new position to the HashSet.
  5. If the loop completes without finding any revisits, return false.

Code:

import java.util.HashSet;

public class PathCrossing {
    public boolean isPathCrossing(String path) {
        // Initialize starting point at (0, 0)
        int x = 0, y = 0;
        
        // Use a HashSet to track visited coordinates
        HashSet<String> visited = new HashSet<>();
        visited.add(x + "," + y);
        
        for (char move : path.toCharArray()) {
            // Update coordinates based on move
            switch (move) {
                case 'N' -> y++;
                case 'S' -> y--;
                case 'E' -> x++;
                case 'W' -> x--;
            }
            
            // Form a unique string for the current position
            String currentPosition = x + "," + y;
            
            // Check if current position is already visited
            if (!visited.add(currentPosition)) {
                return true; // Path crosses itself
            }
        }
        
        // No crossing found
        return false;
    }
    
    public static void main(String[] args) {
        PathCrossing solution = new PathCrossing();
        // Example test cases
        System.out.println(solution.isPathCrossing("NES")); // Output: false
        System.out.println(solution.isPathCrossing("NESWW")); // Output: true
    }
}

Time Complexity:

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI