Guide to Solving Dynamic Array Coding Challenges in Javascript

Liz is kicking off a new series in this video where she focuses on dynamic arrays. Although arrays are often seen as a simpler data structure, dynamic array questions often come up in interviews since they test a baseline understanding of key concepts.

In this video, Liz walks through a dynamic array problem and touches on how memory allocation & amortization works with array resizing.

Coding challenge prompt Liz walks through in the video:
Given an array (arr) of integers, return an array (products) such that products[i] is equal to the product of all the elements of arr except arr[i]. Solve without the division operator in O(n) time.

1:10 The Problem
3:15 The Naive Approach
6:37 The Greedy Approach
11:50 Coding a Javascript Solution
33:22 What are Dynamic Arrays?
34:16 Appending & Amortization
38:24 Recap

Additional Resources:

[stanleyagwu]

Thanks Liz, very smart and clever solution! especially the space adjustment. You and coderbyte team are doing a great job! Thanks

[misterl]

Before wathcing this i try to solve this.
First answer was:
const func1= arr => (
arr.reduce((acc, ele) => {
let sinX = arr.filter(x => x != ele).reduce((acc, ele) => acc * ele)
acc.push(sinX)
return acc
}, [])
)


Second answer was:
const func2= arr => {
let largoArr = arr.length
let res = []
for (let i = 0; i < largoArr; i++) {
let parcial = 1
for (let j = 0; j < arr.length; j++) {
let numeroBlock = arr[i]
if (arr[j] != numeroBlock) parcial *= arr[j]
}
res.push(parcial)
}
return res
}

console.time of both

1.- 9.132ms
2.- 0.525ms

jesus christ, the first one....i think was good :(

[deeptimonga]

Thanks Liz. Well explained !!! Super useful.

[faithmorante]

I really love your walkthroughs, good job

[gouravojha]

// [1, 2, 3, 4, 5]

let arr = [1, 2, 3, 4, 5]
let prod = 1
let res = []
for (let i of arr){
prod = prod * i
}

for (let i of arr){
let otherProd = prod / i
res.push(otherProd)
}
console.log(res)


Most easiest solution with O(N) and space O(N). If you dont store the numbers then its O(1)

[mazthespaz]

this was my first answer before watching your solution: seems fairly quick and uses 2n space to store pre-multiplies. i'm gonna look for better answer before watching your solution. we can also check if zero is in the array because it will make almost every products[] element zero

function findProducts(arrr)
{
let r2l = [];
let l2r = [];
let lprev = 1;
let rprev = 1;
let alen = arrr.length-1;
let results = [];

// create 2 directional product arrays
for( let i = 0; i <= alen; i++ ) {
lprev = l2r[i] = arrr[i] * lprev;
rprev = r2l[alen-i] = arrr[alen-i] * rprev;
}

for( let i = 0; i <= alen; i++ ) {
let prodleft = (i)? l2r[i-1]: 1;
let prodright = (i < alen)? r2l[i+1]: 1;
results[i] = prodleft * prodright; // mult products to left of us by products to the right
}

return results;
}

const arrr = [1, 2, 3, 4];

let products = findProducts(arrr);

console.log( products );

[TheWorpler]

great channel, found my way here from Alvins FCC stuff

[seggsfault]

Hey liz i think it could be done in only one for loop by taking the value of (k) as (arr.length -i) ….u really boiled it down to a simple thing great work