educative.io

Educative

Why do we need to use an external library? Can we solve this without it?

I’m doing Subarrays with Product Less than a Target in JavaScript and it uses an external library: https://www.collectionsjs.com/deque
Can we solve this without using an external library? I’m not clear on how practical is to add a library during an interview, I’d rather find a solution using native JS. Is this Deque used to improve time complexity? Thanks

1 Like

I have the same question, If I use array instead of deque, I am facing some issues for

All Paths for a Sum

Deque is not necessary, it’s probably just a way to maintain a consistent solution across all the different languages. What you need to do though is create a copy of your array like this
function find_subarrays(arr, target) {
let result = []
let left = 0
let product = 1
for (let right = 0; right < arr.length; right++) {
product *= arr[right]
while (product >= target && left < arr.length) {
product /= arr[left]
left += 1
}

const tempList = []
for(let i = right; i >= left; i--) {
  tempList.unshift(arr[i])

  result.push([...tempList])
}

}
return result;
}

Why do we need to make a copy like this?

This is because in javascript when you assign an array to a variable, it doesnt create a copy of the array, it just stores the reference of the array to the variable.
Using joey_y_feng’s example, if we didn’t make a copy, ie:
const tempList = []
for(let i = right; i >= left; i–) {
tempList.unshift(arr[i])
result.push(tempList)
}
What you’re pushing to result is not a copy of tempList but a reference to tempList.
To go through an example, let’s take a look at what that looks like in the 2nd iteration of the outer loop (where right=1):
// tempList starts off empty
const tempList = []
// iterate over inner loop
i=right=1
tempList.unshift(arr[i]) // tempList = [5]
result.push(tempList) // result = [ (reference to tempList) ] = [ [5] ]
// iterate over inner loop
i=right=0
tempList.unshift(arr[i]) // tempList = [2,5]
result.push(tempList) // result = [ (reference to tempList), (reference to tempList) ] = [ [2,5], [2,5] ]
Note, you can see that pushing a reference to temp list is not what we want. What we actually want is to push the actual value of temp list at the time when we push it to result.
Here’s what it looks like with the copy:

// tempList starts off empty
const tempList = []
// iterate over inner loop
i=right=1
tempList.unshift(arr[i]) // tempList = [5]
result.push([...tempList]) // result = [ (copy of tempList) ] = [ [5] ]
// iterate over inner loop
i=right=0
tempList.unshift(arr[i]) // tempList = [2,5]
result.push([...tempList]) // result = [ [5], (copy of tempList) ] = [ [5], [2,5] ]