Counting Array of Arrays

A few weeks ago in a technical interview, I was given a challenge that involved iterating through an arrays. I do not have the exact wording, but it was something akin, to given a family tree in the format of an array of arrays, return all the nodes with only one parent or no parents. To visualize the data, I was shown this:

1   2    4 
 \ /   / | \
  3   5  8  9
   \ / \     \
    6   7     11

From this data display, we can deduce the nodes with only one parent are [5, 7, 8, 9, 11] and the nodes with no parent are [1, 2, 4]. While looking at the data in this format cause me to think "TREE!", this was not the case as this information was given as an array of arrays, with each sub-array including two values, the index at 0 referring to the parent and at index 1 referring to the child. Practically, this looked like:

const parentChildPairs = [
    [1, 3], [2, 3], [3, 6], [5, 6],
    [5, 7], [4, 5], [4, 8], [4, 9], [9, 11]
  ];

I came up with, what I think is, a rather solid linear run-time solution. This involved creating two objects, one to count the number of times parents appear and the other to count the number of times that children appear: let parentsObj = {} and let childObj = {}.

The next step was to iterate over the entire collection and count where numbers appear. If a number appears in a sub-array at index 0, it should be counted as a parent; if it appears in a sub-array at index 1, it should be counted in the child object. Practically, this looks like:

  function findNodesWithZeroAndOneParents(arr){
    let parentsObj = {}
    let childObj = {}
    for (const subArr of arr){
      //count parents
      if (!parentsObj[subArr[0]]){
        parentsObj[subArr[0]] = 1
      } else {
        parentsObj[subArr[0]] += 1
      }
      //count children
      if (!childObj[subArr[1]]){
        childObj[subArr[1]] = 1
      } else {
        childObj[subArr[1]] += 1
      }
    }

The next step is to go through each collection and take out the data that we need: children who have no parents, and children who have only one parent. In both cases, it is extremely helpful to use JavaScript's [Object.keys() method](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/keys), yielding an array of the object keys that can be filtered to get the results that we need.

To find the individuals with no parent, we need to compare the individuals in our parentsObj with those in the childObj. Any key that appears in the parentsObj but no the childObj would be included in the array of individuals with no parent. I chose to do this by finding the keys of the parentObj and then filtering those in relation to the keys of the childObj:

Object.keys(parentsObj).filter(key => !Object.keys(childObj).includes(key))

To find children with only parent requires another Object.keys method but a slightly easier: take all of the keys from the childObj and filter them, finding any key whose value is equal to one (that is, any child who only appears one time at sub-array index one).

Object.keys(childObj).filter(key => childObj[key] === 1)

Once we account for an edge case in which the array fed into the function is empty, we have an answer.

  function findNodesWithZeroAndOneParents(arr){
    if (arr.length === 0) return 0;
    let parentsObj = {}
    let childObj = {}
    for (const subArr of arr){
      if (!parentsObj[subArr[0]]){
        parentsObj[subArr[0]] = 1
      } else {
        parentsObj[subArr[0]] += 1
      }
      if (!childObj[subArr[1]]){
        childObj[subArr[1]] = 1
      } else {
        childObj[subArr[1]] += 1
      }
    }
    let noParents = Object.keys(parentsObj).filter(key => !Object.keys(childObj).includes(key))
    let oneParent = Object.keys(childObj).filter(key => childObj[key] === 1)
    return {"No Parents": noParents, "One Parent": oneParent}
  }

NB: Because JavaScript does not allow return on multiple variables, I returned the answer as an object, with the keys referring to the different information needed and their values referring to the appropriate arrays.