Javascript: Concise way to fill sparse array with object

Question

I am using an array to store objects (directed edges between nodes) and would like to use the an array to store the objects such that I can use the index of the array to refer to the object id.

 /**
 * Take a graph where 
 * @param {number} N: The number of Nodes of in the graph
 * @param {number[][]} trust: an array of directed edges trust [[a,b]] draws 'a trusts b'
 * @return {number} 
 */
var findJudge = function(N, trust) {
    let nodes = [
        {
            trusts: {},
            trustedBy: {}
        }
    ]    

    trust.forEach(pair => {
        nodes[pair[0]].trusts = pair[1]
        nodes[pair[1]].trusted = pair[0]
    })    
    return -1
};

Sample input: N = 2 and trust = [[1,2]] errors because nodes[2] doesn't exist yet at runtime.

I would like to avoid pre-filling the array with null values if possible in the event that N is a really large number. Perhaps this is not the proper data structure for filling sparse adjacency lists. Is there a way to say var x = new Array(of type object, of length N)?

Im open to any and all solutions.

Edit to show context of problem https://leetcode.com/problems/find-the-town-judge/description/

Sample input and expected output would help to make your point clearer — Yevhen Horbunkov
– Yevhen Horbunkov, Commented Jun 16, 2020 at 18:42
Just check whether it exists and create it if it doesn't but you need it. — Bergi
– Bergi, Commented Jun 16, 2020 at 18:44
Please incorporate the context into the question. If that link goes down, this question remains without context. — Heretic Monkey
– Heretic Monkey, Commented Jun 16, 2020 at 19:11
Apart from your question, please note that you would be overwriting the trusts and trusted properties when they already had a value. You cannot assume that a person only trusts one other person at the most. So, I think you need to review your idea. — trincot
– trincot, Commented Jun 16, 2020 at 19:51

trincot · Accepted Answer · 2020-06-16 21:06:59Z

I would like to avoid pre-filling the array with null values if possible in the event that N is a really large number.

You can avoid such extreme case by first checking the size of the trust argument. If there is a solution, then at least trust.length >= N-1.

If however that test passes, then you will anyway need to look at all entries of trust to determine whether there is a judge, and who it is. So then it does not increase the time complexity of the work if you also create all N nodes, before even iterating over trust.

Secondly, your code would currently overwrite information, so that you can only store one trusted person and one trusted-by person per node. What you really need is that trusted and trustedBy can store multiple entries; at least when you want to make a double-threaded graph.

But when you really think about it, you would have enough information if you would only know the count of trusted and the count of trustedBy a node has. The judge must be the one for which the trusted count is zero and the trustedBy count is N-1. There cannot be two of those, as that would be a contradiction.

So, you can avoid creating the graph. It is enough that you just store counts, that start with 0.

As in JavaScript array indices start with zero and not 1, your nodes array would be indexed by one less than the actual person-id that is used in the trust array.

Here is how that code could look:

var findJudge = function(N, trust) {
  // Quick exit, to avoid unnecessary looping
  if (trust.length < N - 1) return -1;

  // Create all nodes (with index one less -- starting at 0)
  let nodes = Array.from({
    length: N
  }, () => ({
    trusts: 0,
    trustedBy: 0
  }));
  // Count trust relationships in both directions
  trust.forEach(([trustedBy, trusted]) => {
    nodes[trustedBy - 1].trusts++;
    nodes[trusted - 1].trustedBy++;
  });
  // The only judge meets the following requirements
  // Add one to the found judge to go from 0-based to 1-based.
  return nodes.findIndex(node => node.trusts == 0 && node.trustedBy == N - 1) + 1 || -1;
};

console.log(findJudge(3, [[1,2],[3,2],[1,3]]));

If you care about speed, then replace all loops with old-style for loops, and instead of the array of objects (trust), use two simple arrays of counts (trusts and trustedBy), as arrays of integers usually lead to better execution times than arrays of objects.

Kevin Crum · Accepted Answer · 2020-06-16 19:50:09Z

0

as per @Bergi suggestion I simply check if object exists or not and create it. Still curious to other suggestions if anyone has any other javascript wizardry

var findJudge = function(N, trust) {
    function node() {
        trusts: {}
        trustedBy: {}
    }
    let nodes = []

    trust.forEach(pair => {
        pair.forEach(element => {
            if (nodes[element] === undefined)
                nodes[element] = new node()
        })
        nodes[pair[0]].trusts = pair[1]
        nodes[pair[1]].trusted = pair[0]
    })    
    return -1
};

Would have posted this as a comment however comments don't allow for code block formatting.

answered Jun 16, 2020 at 19:50

Kevin Crum

1953 silver badges18 bronze badges

Collectives™ on Stack Overflow

Javascript: Concise way to fill sparse array with object

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related