algoadvance

Leetcode 1496. Path Crossing

Problem Statement

  1. Path Crossing

Given a string path, where path[i] ∈ {‘N’, ‘S’, ‘E’, ‘W’}, each character representing a move north, south, east, or west, respectively. Initially, you start at the origin (0, 0) on a 2D plane. Return true if the path crosses itself at any point; otherwise, return false.

Example:

  1. Input: path = “NES” Output: false
  2. Input: path = “NESWW” Output: true

Clarifying Questions

  1. Can the path be an empty string?
    • Answer: It is unlikely based on the context of the problem.
  2. Is the path constrained to a certain length?
    • Answer: It is typical for constraints to be in the problem description, but let’s assume it can be sufficiently large to test the solution’s efficiency.

Strategy

  1. Use a set to record each position visited.
  2. Keep track of the current position starting from the origin (0, 0).
  3. For each character in the string, update the current position.
  4. Check if the new position already exists in the set:
    • If it does, return true (path crosses itself).
    • If it doesn’t, add the new position to the set.
  5. If none of the positions repeat at the end of the loop, return false.

Time Complexity

Code

#include <iostream>
#include <unordered_set>
#include <string>

bool isPathCrossing(std::string path) {
    std::unordered_set<std::string> visited;
    int x = 0, y = 0;
    visited.insert("0,0");

    for (char dir : path) {
        if (dir == 'N') {
            ++y;
        } else if (dir == 'S') {
            --y;
        } else if (dir == 'E') {
            ++x;
        } else if (dir == 'W') {
            --x;
        } else {
            // Invalid Input
            return false;
        }

        std::string position = std::to_string(x) + "," + std::to_string(y);
        if (visited.find(position) != visited.end()) {
            return true;
        }
        visited.insert(position);
    }

    return false;
}

// Example usage
int main() {
    std::string path1 = "NES";
    std::string path2 = "NESWW";
    
    std::cout << isPathCrossing(path1) << std::endl;  // Output: false
    std::cout << isPathCrossing(path2) << std::endl;  // Output: true
    
    return 0;
}

Explanation:

  1. Initialization: Defines a set visited to track all visited positions and initializes start position (0, 0).
  2. Loop through path: Updates position based on direction, creates a string representation of new position.
  3. Check for crossing: If the position already exists in the visited set, returns true.
  4. End of loop: If no repeats found, returns false.

Adjust the code and input handling if there are additional constraints or edge cases specified.

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