1496 Path Crossing

Description

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

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

Example 2

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

Constraints:

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

Solution

In this case, we want to know if we visited the same point again in our traversal. Again, we can store these points we have visited in some hash data structure and track if we had already visited this point. Now, the problem can be divided into two parts, calculating current position from the traversal character and second is keeping track of these positions in the form of x and y coordinates in Hash data structure.

1. In order to convert each movement into their respective position, we simply have modify one of the coordinates. The problem states that we are moving only one unit with each character.

   • For N or north, move only Y coordinate by +1.
   • For S or south, move only Y coordinate by -1.
   • For E or east, move only X coordinate by +1.
   • For W or west, move only X coordinate by -1.

To store X and Y coordinates, we can use tuple or Java Pair, however, I have used List to track these two coordinates. list(0) represents X coordinate and list(1) represents Y coordinate.

2. To store these coordinate points, we need a data structure. We can use them as a string separated by comma or some other charactes like x,y or x:y format or again, we can use a data structure that has hashCode defined. In this solution, I have used List<Integer>

 1class Solution {
 2    public boolean isPathCrossing(String path) {
 3        List<Integer> currentPosition = new ArrayList<>(Arrays.asList(0, 0));
 4        Set<List<Integer>> visitedPositions = new HashSet<>();
 5        visitedPositions.add(currentPosition);
 6        for (char c: path.toCharArray()) {
 7
 8            switch (c) {
 9                case 'N':
10                    currentPosition = new ArrayList<>(Arrays.asList(
11                        currentPosition.get(0), currentPosition.get(1) + 1)
12                        );
13                    break;
14                case 'S':
15                    currentPosition = new ArrayList<>(
16                        Arrays.asList(currentPosition.get(0), currentPosition.get(1) - 1)
17                        );
18                    break;
19                case 'E':
20                    currentPosition = new ArrayList<>(
21                        Arrays.asList(currentPosition.get(0) + 1, currentPosition.get(1))
22                        );
23                    break;
24                case 'W':
25                    currentPosition = new ArrayList<>(
26                        Arrays.asList(currentPosition.get(0) - 1, currentPosition.get(1))
27                        );
28                    break;
29            }
30
31            if (visitedPositions.contains(currentPosition)) {
32                return true;
33            }
34            visitedPositions.add(currentPosition);
35        }
36        return false;
37    }
38}

• Time Complexity: O(n)
• Space Complexity: O(n)