1

I am creating a 2D array using the following code:

let arr = new Array(3);
for (let i = 0; i < 5; i++){
    arr[i] = new Array(5);
}

And then I try to populate it using this code:

for(let i = 0; i < arr.length; i++){
    for (let j = 0; j < arr[i].length; j++){
        arr[i][j] = 0;
    }
}

This code works, but the time complexity is O(n^2). Is there any better way to do this?

Penny Liu
  • 15,447
  • 5
  • 79
  • 98
Ian Halstead
  • 78
  • 1
  • 1
  • 10
  • 1
    This related 1-D question may be useful: https://stackoverflow.com/questions/1295584/most-efficient-way-to-create-a-zero-filled-javascript-array – cybersam Feb 26 '20 at 01:50
  • I can't think of anything with a guaranteed sub-quadratic complexity. Well, depends on the implementation but stuff like `fill` might still do an iteration. Creating one array and copying it multiple times might still be ultimately quadratic if the copy is `O(n)`. You can, however, use typed arrays which will be pre-initialised. Or you can lazily initialise the arrays by property access - you just get a `m` by `n` matrix and then when you access an index initialise it as zero if not set. Proxies might help with this approach. – VLAZ Feb 26 '20 at 02:13
  • 1
    Creating an object that is size O(n^2) is going to be O(n^2) due to the nature of information. You may be able to get the constant really small, or you may be able to go faster if you change the rules (e.g., generate the elements on demand), but as-written you can't create O(n^2) data faster than O(n^2). – Raymond Chen Feb 26 '20 at 02:23

1 Answers1

2

Not sure how internally it does, But this is simpler way using language API instead of doing our own.

const arr = Array.from({length: 5}, () => new Array(5).fill(0));

console.log(arr);
Siva K V
  • 10,561
  • 2
  • 16
  • 29