Business
Jobs
  • About Us
  • Solutions
    • Job Postings
      Post your job and receive qualified candidates in 48h.
    • Candidate Assessments
      500+ technical and psychological tests, plus anti-fraud.
    • Headhunting
      Tailor-made executive search from start to finish.
    • Payroll + EOR
      Payroll dispersal and EOR across 15+ LATAM countries.
  • Pricing
  • Jobs

0

424
Views
Finding the longest chain of array element indices and values

I can't solve a problem. We have an array. If we take a value, the index of it means port ID, and the value itself means the other port ID it is connected to. Need to find the start index of the longest sequential connection to element which value is -1.

I made a graphic explanation to describe the case for the array [2, 2, 1, 5, 3, -1, 4, 5, 2, 3]. On image the longest connection is purple (3 segments).

graphic description

I need to make a solution by a function getResult(connections) with a single argument. I don't know how to do it, so i decided to return another function with several arguments which allows me to make a recursive solution.

function getResult(connections) {
  return f(connections.findIndex(e => e === -1), connections, 0, []);
}

function f(index, cnx, counter, branches) {
  counter++;  
  for (let i = 0; i < cnx.length; i++) {
    if (cnx[i] === index) {
      branches.push([i, counter]);
      return f(i, cnx, counter, branches);
    }
  }
  return branches.sort((a, b) => b[1] - a[1])[0][0];
}

console.log(getResult([1, 2, -1])); // expected 0
console.log(getResult([1, -1, 1, 2])); // expected 3
console.log(getResult([2, 1, -1])); // expected 0
console.log(getResult([3, 4, 1, -1, 3])); // expected 2
console.log(getResult([1, 0, -1, 2])); // expected 3
console.log(getResult([3, 2, 1, -1])); // expected 0
console.log(getResult([2, 2, 1, 5, 3, -1, 4, 5, 2, 3])); // expected 6

Anyway, the code doesn't work completely properly. Would you please explain my mistakes? Is it possible to solve the problem by a function with just one original argument?

over 4 years ago · Santiago Trujillo
1 answers
Answer question

0

The code doesn't work completely properly. Would you please explain my mistakes?

You were quite close. The main problem is that the return keyword in front of the recursive calls terminates the for loop and the entire f function prematurely. This will cause it to visit only the nodes on the first possible branch, not all of them.

The other issue is that branches might be empty at the end of the function, yet you still access [0][0]. Instead return the entire array from f, and access the first tuple on in getResult.

These two small fixes already make the function work1:

function getResult(connections) {
  return f(connections.findIndex(e => e === -1), connections, 0, [])[0][0];
}

function f(index, cnx, counter, branches) {
  counter++;  
  for (let i = 0; i < cnx.length; i++) {
    if (cnx[i] === index) {
      branches.push([i, counter]);
      f(i, cnx, counter, branches);
    }
  }
  return branches.sort((a, b) => b[1] - a[1]);
}

console.log(getResult([1, 2, -1])); // expected 0
console.log(getResult([1, -1, 1, 2])); // expected 3
console.log(getResult([2, 1, -1])); // expected 0
console.log(getResult([3, 4, 1, -1, 3])); // expected 2
console.log(getResult([1, 0, -1, 2])); // expected 3
console.log(getResult([3, 2, 1, -1])); // expected 0
console.log(getResult([2, 2, 1, 5, 3, -1, 4, 5, 2, 3])); // expected 6
1: Actually, there's an edge case where it still doesn't work: when called on the empty array as getResult([]), it shouldn't throw an exception if branches is empty. This can be fixed by an specifically handling that case with an if condition, or by including the tuple [-1, 0] (no node, distance 0) in the branches.

Additional improvements would be to do also the sorting only once at the end in getResult, and starting the search directly with f(-1, connections, 0, []); instead of using findIndex.

Is it possible to solve the problem by a function with just one original argument? I don't know how to do it, so i decided to return another function with several arguments which allows me to make a recursive solution.

Introducing a helper function is a totally appropriate solution, this approach is good!

While it's always possible to write a recursive scheme as a loop with an explicit stack, that is usually unwieldy and incomprehensible. With the DFS approach you chose, a recursive function is the easiest and cleanest way to write it.

If you don't want to create an extra global variable, you can even declare your helper function inside getResult. This also allows accessing the connections directly from the upper scope, instead of passing it in as a function parameter. The same can be done to the branches variable:

function getResult(connections) {
  const branches = [];
  function f(index, distance) {
    branches.push([index, distance]);
    for (let i = 0; i < connections.length; i++) {
      if (connections[i] === index) {
        f(i, distance+1);
      }
    }
  }
  f(-1, 0);
  branches.sort((a, b) => b[1] - a[1]);
  return branches[0][0];
}

console.log(getResult([1, 2, -1])); // expected 0
console.log(getResult([1, -1, 1, 2])); // expected 3
console.log(getResult([2, 1, -1])); // expected 0
console.log(getResult([3, 4, 1, -1, 3])); // expected 2
console.log(getResult([1, 0, -1, 2])); // expected 3
console.log(getResult([3, 2, 1, -1])); // expected 0
console.log(getResult([2, 2, 1, 5, 3, -1, 4, 5, 2, 3])); // expected 6

As for further alternatives and optimisations:

  • you could use an iterative BFS with a queue. Notice that although your input format generally is a graph, the connected component that you will traverse is guaranteed to be a tree rooted at -1, with each child node pointing to its parent, never forming a circle (since there is no node -1 that points anywhere).
  • instead of keeping around all "branches" (node indices with their distance) around in a list, keep only the one with the maximum distance you encountered so far.
  • instead of repeatedly iterating the connections array to find children of a node (the is referencing the current index), build an actual tree structure in a single iteration of the connections, then traverse that tree to find the deepest branch.
over 4 years ago · Santiago Trujillo Report
Answer question
Find remote jobs

Discover the new way to find a job!

Top jobs
Top job categories
Business
Post vacancy Pricing Sales
Legal
Terms and conditions Privacy policy
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Show me some job opportunities
There's an error!