Big O of two sum

1

#Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

##Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Here is my solution.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    return nums.reduceRight((ans,val,idx,arr)=>{
        const remainder =  target - val;
        const idx2 = arr.indexOf(remainder);
        return (idx !== idx2 && idx2 !== -1)?[idx, idx2]: ans;
    },[]);

I’m thinking this is the best answer because O(n) but would like feedback.

2

You should put your topic in ‘Help’ not in ‘Project feedback’ as it’s about algorithms

2 Likes
3

I don’t think it’s O(n), but O(n2) in the worst case, because of the .indexOf() call in the callback (I assume .indexOf is O(n) in the worst case).

2 Likes
4

I guess I’ve been assuming .indexOf() was working at something better than O(n) but even so wouldn’t it be O(n) + O(n) and not O(n) * O(n)?

5

Anytime you have to search through a dataset of n, the runtime will be O(n). If for each element in the dataset you have to search through the dataset again, then it’s O(n^2). So in this case where for every element, you’re searching the array to find if there is a matching element such that a + b = target, it would be O(n^2). There’s a way to do it in O(n) using what’s called a “greedy” approach where you keep track of what you’ve seen as you iterate through the array so when you come upon a number that matches the condition a + b = target you return that number. Hint, you’ll need to use additional space to store the values you’ve seen. Is O(n) the best we could do? Yes because we know that we may have to look at every element in the array to get the answer.

1 Like
6

I came up with O(n2) because I think you’re calling .indexOf (which I assume to be O(n) in the worst case) at most n times, like in a nested loop

1 Like