Can you try to explain, in words what each line in your code is doing? I think you have some good parts but they aren’t working together in a cohesive ‘big picture’ to get the answer.
function pairwise(arr, arg) {
//copyOfArr just points to the same array as arr
let copyOfArr=arr;
console.log(copyOfArr === arr) //true
//you can double loop through the same array without out
//the need for a copy
let sumOfAddedNum=[];
let indeces=[];
let sumOfIndeces=[];
for(let i=0;i<copyOfArr.length;i++){
for(let j=0;j<arr.length;j++){
sumOfAddedNum.push(copyOfArr[i]+arr[j])
//You already have access to the index,
//the index is i or j,
//also indexOf only gets the first intances of
//an element so this would not work for repeated elements
indeces.push(copyOfArr.indexOf(copyOfArr[i]))
indeces.push(arr.indexOf(arr[j]))
}
}
for(let i=0;i<sumOfAddedNum.length;i+=1){
sumOfIndeces.push(indeces[i]+indeces[i+1])
}
console.log(sumOfAddedNum,indeces,sumOfIndeces)
}
pairwise([1,4], 5);
This is commenting out somethings that are probably not working the way you think they are. If you would, write out what you want to do in whatever your primary language is and then try to do that in code. If you write out you want to do as a comment I can help you with the logic of it.
function pairwise(arr, arg) {
let indecesOfElementPairs=[]
for(let i=0;i<arr.length;i++){
//you should not be looking at elements
//you have already passed
for(let j= 0;j<arr.length;j++){
//if this block executes both indexes can no longer be used
//and you should break the loop for the same reason.
//you should invalidate any indexes that have been valid
if(arr[i]+arr[j]===arg){
indecesOfElementPairs.push(i,j)
//invalidate indexes here
//stop loop here
}
}
}
//You do not need uniq if you get the above comments to work
let uniq = [...new Set(indecesOfElementPairs)];
console.log(indecesOfElementPairs,uniq)
}
pairwise([1, 1, 1], 2);
I got the code to pass with a bit of refactoring, if you have any further questions feel free to ask
I am not an expert with time complexity and its notation, but I believe my personal solution would have been O(n*log(n)). I used the following logic:
//obj = create an object to save what I've used {};
//sum = 0, to be the return value
/*
for elements of a given list {
check obj in constant time
if (obj[element has been used]) skip element
for elements after given element in list {
if (element[i] + element[j] === v) {
obj[j] = value has been used
sum = sum + (i + j)
break loop as i has been used
}
}
}
return sum
/*
In this example the amount of elements you loop through decreases each iteration so it is not o(n ^ 2).
In your current example it would be essentially a double loop as you are not providing a second argument to includes which means it will loop through the entirety of the array and while having two includes in your use does not increase time complexity it will cause it to take longer as it simply has more work to do.
yea i see your example is making a cache… memoization…
I could have used find instead… I just wanted to solve the problem fast… but thats moot. yeah I see your example above is probably a better way to go about it…
why start i and j both at zero, and then only afterwards you add it all? efficient way is how @caryaharper mentioned. with a cache…
you understand why what you wrote is not so good?
we should not use includes… look again at the pseudocode of what caryaharper wrote. if you use a cache it will be instant lookup:
the above screenshot i think could be referring to when multiple things hash to the same key, (bucket size is small) then you would have to iterate through the linked list at that spot(key) to find it and it would take time… But in javascript object I think its instant you will never have more than one at the same key.
The best you can do is an O(n^2) algo. In the worst case:
The first item needs to be compared against n-1 items
The second item needs to be compared against n-2 items
…
The second to last item needs to be compared against 1 item
So we have ((n-1) * n) / 2 === (n^2 - n)/2 element comparisons
The real savings is in how you check if an index has been used.
There are two basic multi-element data structures in JavaScript, the array and the object.
Option 1) Use an array - so long as your array is allocated up-front, it is O(1) to index into an array or modify the array
Option 2) Use an object - this can also be O(1) to index, but the constant is bigger for hash lookups than array lookups for relatively small arrays (In JS, maybe < 1 million elements? I’m not sure)
The question is how to store the data in the object or array. This affects how well you can look up the data.
For an array, you can either keep an array of all visited indices or you can keep a boolean array that keeps the visited status of each index. One is much faster than the other.
For an object, I’d just add the index as a property if it has been visited and leave it unset if it has not.
