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.

Submit your solution at: https://leetcode.com/problems/self-crossing/

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.

1

(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   

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

1

(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   

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:

1

(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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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 (The Ultimate Computing & Technology Blog) —