1. Runtime Distribution

2. Submission Details

3. Description

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.

4. Code

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active"]

public boolean isSelfCrossing(int[] x){
	int length = x.length;
	
	if(length < 4){
		return false;
	}
	
	for(int i = 3; i< length;i++){
		if(x[i] >= x[i-2] && x[i-3] >= x[i-1]){
			return true;
		}
		if(i > 3 && x[i] + x[i-4] >= x[i-2] && x [i-1] == x[i-3]){
			return true;
		}
		if(i > 4 && x[i-1] + x[i-5] >= x[i-3] && x[i-3] >= x[i-1] 
				&& x[i] + x[i-4] >= x[i-2] && x[i-2] >= x[i-4]){
			return true;
		}
	}
	return false;
}

[/restab]
[/restabs]

5.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active"]

import org.junit.Test;

public class LeetCode0335 {

	public boolean isSelfCrossing(int[] x){
		int length = x.length;
		
		if(length < 4){
			return false;
		}
		
		for(int i = 3; i< length;i++){
			if(x[i] >= x[i-2] && x[i-3] >= x[i-1]){
				return true;
			}
			if(i > 3 && x[i] + x[i-4] >= x[i-2] && x [i-1] == x[i-3]){
				return true;
			}
			if(i > 4 && x[i-1] + x[i-5] >= x[i-3] && x[i-3] >= x[i-1] 
					&& x[i] + x[i-4] >= x[i-2] && x[i-2] >= x[i-4]){
				return true;
			}
		}
		return false;
	}
	
	@Test
	public void test(){
		int [] x = {2, 1, 1, 2};
		System.out.println(isSelfCrossing(x));
	}
}

[/restab]
[/restabs]