Looking for a little help to solve this problem below. I have solved it by storing all coordinates for each move however I don't think that meets the time & space complexity requirements.

Also it mentions being able to modify the input array.
That almost feels like a tip or part of a possible solution.

disclaimer... This not a homework assignment & I am not going to try to pass off any solution as my own. I am just curious, and annoyed :)

I'm using C#

A non-empty zero-indexed array A of N positive integers is given. A LOGO turtle stands at (0,0) heading North. It moves A[0] steps forward and turns by 90 degrees clockwise. Then it moves A[1] steps forward and turns clockwise by 90 degrees. And so on.

For example, given: A[0] = 1 A[1] = 3 A[2] = 2 A[3] = 5 A[4] = 4 A[5] = 4 A[6] = 6 A[7] = 3 A[8] = 2

The turtle walks as follows: (0, 0) -> (0, 1) 1st move, 1 step North (0, 1) -> (3, 1) 2nd move, 3 steps East (3, 1) -> (3, -1) 3rd move, 2 steps South (3, -1) -> (-2, -1) 4th move, 5 steps West (-2, -1) -> (-2, 3) 5th move, 4 steps North (-2, 3) -> (2, 3) 6th move, 4 steps East (2, 3) -> (2, -3) 7th move, 6 steps South (2, -3) -> (-1, -3) 8th move, 3 steps West (-1, -3) -> (-1, -1) 9th move, 2 steps North

In the 7th and 9th moves the turtle touches its previous path, namely: at point (2, 1) in the 7th move at point (2, -1) in the 7th move at point (-1, -11) in the 9th move

Write a function: class Solution { int solution(int[] A); } that, given a description of the turtle’s walk in array A, returns the number of the first move in which the turtle touches its previous path, or 0 if no such situation occurs. For example, given array A as defined above, the function should return 7, because the turtle touches its previous path at point (2, 1) in the 7th move.

Assume that: N is an integer within the range [1..100,000]; each element of array A is an integer within the range

Complexity: expected worst-case time complexity is O(N); expected worst-case space complexity is O(1), beyond input storage (not counting the storagerequired for input arguments).

Elements of input arrays can be modified.

public static int Run(int[] input)
{
    for (int i = 3; i < input.Length; i  )
    {
        if (input[i - 1] <= input[i - 3]) //If touching previous path is possible on this move
        {
            if (input[i] >= input[i - 2]) //this move >= opposite side
                return i   1;

            if (1 == 0) //At least 1 other case here, but i'm stumped
                return i   1;
        }
    }
    return 0;

}

CodePudding user response：

I don't know if this is the best solution, but I think you need to go back 4 or 5 from the current index to check those to see if the path could cross:

public static int Run(int[] input)
{
    for (int i = 3; i < input.Length; i  )
    {
        if (input[i-1] <= input[i-3]) //If touching previous path is possible on this move
        {
            if (input[i] >= input[i-2]) //this move >= opposite side
                return i   1;

            int fourBack = i >= 4 ? input[i-4] : 0; // Handle case where i < 4
            int fiveBack = i >= 5 ? input[i-5] : 0; // Handle case where i < 5

            if (input[i-1] >= input[i-3] - fiveBack 
             && input[i]   >= input[i-2] - fourBack 
             && input[i-2] >= fourBack)
                return i   1;
        }
    }

    return 0;
}