# C++ Coding Exercise – Self Crossing

You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to the north, then x[1] metres to the west, x[2] metres to the south, x[3] metres to the east and so on. In other words, after each move your direction changes counter-clockwise.

Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.

leetcode-self-crossing

### When n is less than 3

We can easily figure out that if n is smaller than 3 and the answer is false because all input are positive numbers (not zero) so three edges will not cross.

### When n is 4

It will cross like this:

`┌───┐ │   │ └───┼──>     │`
`┌───┐ │   │ └───┼──>     │`

So the condition is to check the fourth edge with the second and the first with the third.

`(x[3] >= x[1] && (x2]) <= x[0])`
`(x[3] >= x[1] && (x2]) <= x[0])`

### When n is 5

There is another special case with n=5.

`┌──────┐ │      │ │      │ │      │ └──────/ <--this is a square corner  `
`┌──────┐ │      │ │      │ │      │ └──────/ <--this is a square corner`

5 edges form a rectangle where the last edge plus the first edge equal or bigger than the third edge.

`(x[3] == x[1] && x[4] + x[0] >= x[2])`
`(x[3] == x[1] && x[4] + x[0] >= x[2])`

### When n is 6

This is a special case that requires at least 6 edges:

`┌──────┐ │      │<_____ │      │     │ │            │ └────────────/  <--this is a square corner  `
`┌──────┐ │      │<_____ │      │     │ │            │ └────────────/  <--this is a square corner`

The last edge crosses the first edge. In order for this happen:

1. Edge 4 is bigger than Edge 2
2. Edge 6 is bigger than (Edge 4 – Edge 2)
3. Edge 5 is bigger than (Edge 3 – Edge 1)
4. Edge 5 is smaller than Edge 3

Using code:

`(x[3] >= x[2] && x[5] >= x[3] - x[1] && x[4] >= x[2] - x[0] && x[4] <= x[2])`
`(x[3] >= x[2] && x[5] >= x[3] - x[1] && x[4] >= x[2] - x[0] && x[4] <= x[2])`

### Generalization

So the idea is to check for every possibilities of self-crossing, return true if found any. When all checks are performed and no crossings are found, the function returns false.

The O(n)algorithm does the one-scan pass. Checking for last-4 edges, last-5 edges and last-6 edges at each iteration turns the shape 90 degree. The non-self-crossing edges are checked and can be disregarded immediately.

`class Solution { public:     bool isSelfCrossing(vector<int>& x) {         for (int i = 3; i < x.size(); i ++) {             if (x[i] >= x[i - 2] && (x[i - 1]) <= x[i - 3]) {                 return true;             }             if (i >= 4) {                 if (x[i - 1] == x[i - 3] && x[i] + x[i - 4] >= x[i - 2]) {                     return true;                 }             }             if (i >= 5) {                 if (x[i - 2] >= x[i - 4] && x[i] >= x[i - 2] - x[i - 4] && x[i - 1] >= x[i - 3] - x[i - 5] && x[i - 1] <= x[i - 3]) {                     return true;                 }             }         }         return false;     } };`
`class Solution { public:     bool isSelfCrossing(vector<int>& x) {         for (int i = 3; i < x.size(); i ++) {             if (x[i] >= x[i - 2] && (x[i - 1]) <= x[i - 3]) {                 return true;             }             if (i >= 4) {                 if (x[i - 1] == x[i - 3] && x[i] + x[i - 4] >= x[i - 2]) {                     return true;                 }             }             if (i >= 5) {                 if (x[i - 2] >= x[i - 4] && x[i] >= x[i - 2] - x[i - 4] && x[i - 1] >= x[i - 3] - x[i - 5] && x[i - 1] <= x[i - 3]) {                     return true;                 }             }         }         return false;     } };`

–EOF–

GD Star Rating