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

Example 1:

  Given x = [2, 1, 1, 2],
  ┌───┐
  │   │
  └───┼──>


  Return true (self crossing)

Example 2:

  Given x = [1, 2, 3, 4],
  ┌──────┐
  │      │


  └────────────>

  Return false (not self crossing)

Example 3:

    Given x = [1, 1, 1, 1],
    ┌───┐
    │   │
    └───┼>

    Return true (self crossing)
 #include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>

using namespace std;

void print1D(vector<int> &nums) {
    for (auto i : nums) cout << i << ' ';
}


/* method:
- 
*/
bool isSelfCrossing(vector<int>& x) {
    int up, left, down, right = 0;
    int nextUp, nextLeft, nextDown, nextRight = 0;

    int indexCounter = -1;

    while (indexCounter <= x.size()) {
        up += x.at(indexCounter++);
        left += x.at(indexCounter++);
        down += x.at(indexCounter++);
        right += x.at(indexCounter++);

        if (indexCounter <= x.size()) {

        }
        nextUp += x.at(indexCounter++);
        nextLeft += x.at(indexCounter++);
        nextDown += x.at(indexCounter++);
        nextRight += x.at(indexCounter++);

        // check intersection of two fieldbox's
        if (right >= left || nextUp >= down || nextLeft >= left || nextDown >= down) return false;

        // test cases passed, update next field box
        left = nextLeft;
        down = nextDown;
        right = nextRight;
        up = nextUp;
    }
    return true;

}

int main()
{
    vector<int> test = { 1, 1, 1, 1 };
    isSelfCrossing(test);
    print1D(test);
}

Last updated