Exercise with loops and arrays

Question

While practicing programming on coding challenges I ran into this problem and I'm stuck on it. You have two arrays:

int[] fromArray
int[] toArray

They hold values of 'nodes' (from and to node). Index are related like this fromArray[1] -> toArray[1], fromArray[2] -> toArray[2], .... It is something like linked lists. So for example in fromArray on index 0, you have value 1, and then on index 0 in toArray you have 4. Then you have for example on index 2 in fromArray value 4, and on index 2 in toArray value 9. This means that value 1 is connected to 4, and 4 is connected to 9.

I need to find last node (node that doesn't have connected node). If there is no such, then it's circular, and I need to print last node before it becomes circular.

This is standard example, result should be 8:

int[] fromArray = new int[] {1, 4, 6, 2};
int[] toArray = new int[] {4, 6, 8, 5};

As special case we have circular list, e.g.

int[] fromArray = new int[] {1, 4, 6, 2};
int[] toArray = new int[] {4, 6, 1, 5};

The result should be 6 (that is the last node before connecting 1 to 1 (making this list circular)..

This was my closest try, but still I think that I'm nowhere the right path to solve this. I thought that I can solve this by finding which element is in toArray but isn't in fromArray, but that is not the right solution:

public static int findLastNode(int[] fromArray, int[] toArray){
    int lastNode = -1;
    boolean found = false;
    int index = -1;
    for (int i = 0; i < fromArray.length; i++){
        for (int j = 0; j < fromArray.length; j++){
            if (toArray[i] == fromArray[j]){
                found = true;
            }
        }
        if (found){
            found = false;
        }
        else {
            lastNode = toArray[i];
            return lastNode;
        }
       
    }
    for (int i = 0; i < toArray.length; i++){
        for (int j = i+1; j < toArray.length; j++){
            if (toArray[i] == toArray[j]){
                lastNode = toArray[i];
            }
        }
    }
    return lastNode;
}

Answer 1

You will need to walk through your graph from one node to the next until either there is no next node or the next node is your starting node, fromArray[0]. So code a loop to take such steps. You will want to have a variable for the current index into both arrays, the index of the current edge, so to speak. Whenever toArray[currentIndex] == fromArray[0], you have detected a cycle. In this case return the node before the first node, that is, fromArray[currentIndex]. You can put the return statement inside your if statement inside your loop.

Each time through your loop try to find the next edge, that is, the index i where fromArray[i] == toArray[currentIndex]. You may use an inner loop or a stream pipeline. If there is no such index, you have found the last node. Return it.

Answer 2

You are overthinking it. Try to take it step by step and write them on a piece of paper.

You know for sure that fromArray[0] is "linked" to toArray[0]. In that case you can assume that lastNode will be toArray[0] even before you will run your algorithm. After that, you need to check if there are any "linked values" in fromArray. If yes, change lastNode to toArray at the index of that link.

Now, you need to think about the case, when the links are circular.

The circularity is when lastNode is same as our fromArray[0], since it is starting point of our links. So if, the lastNode is equal to fromArray[0], you need to return value from fromArray at the same index that lastNode was found. To avoid second loop (to find that index), you can save it into the variable lastNodeIndex.

Finally, we end up with this algorithm:

public static int findLastNode(int[] fromArray, int[] toArray) {
        int lastNode = toArray[0];
        int lastNodeIndex = 0;
        for (int i = 1; i < fromArray.length; i++) {
            if (fromArray[i] == lastNode) {
                lastNode = toArray[i];
                lastNodeIndex = i;
            }
        }
        return lastNode == fromArray[0] ? fromArray[lastNodeIndex] : lastNode;
    }