SDE - 1

Let's come from afar for this problem.

Slow & simple solution

The bruteforce solution for this will be going over the array, and for each element running another for loop, checking if the sum of the elements will be target, leaving us with O(n^2) time complexity. So how to optimize this?

Important idea

One important idea is the look-up. So, for each element of the array, we're not looking for the needle in the haystack, but asking the needle to jump out of it. In other words, for each nums[i], we wonder if there's a target / nums[i] in our array. Now we do n steps, and on each step do a look-up, which takes x time. Leaving us with O(n*x).

Set

We want to use a data structure with minimal look-up time here, so let's create a new Set Populate it with all the numbers. And on each step look up, if our desired pair is there.

p.s. Set.prototype.has() has a time complexity below O(n), which can be from O(1) to O(logn) based on internal implementation. O(1) is the hash-map.

var twoSum = function (nums, target) {
const S = new Set(nums);
for (let i = 1; i < nums.length; i++) {
if (S.has(target - nums[i])) {
return [nums.indexOf(target - nums[i]), i];
}
}
};
Optimization

To optimize this further, we can populate the Set on the go, because for each step, we look into all the previous numbers, no cases missed, yet some potential for early exits giving us a little boost.

var twoSum = function (nums, target) {
const S = new Set([nums[0]]);
for (let i = 1; i < nums.length; i++) {
if (S.has(target - nums[i])) {
return [nums.indexOf(target - nums[i]), i];
}
S.add(nums[i]);
}
};

Tip 1 : Make sure your resume is up-to-date
Tip 2 : Be confident and focus on your communication
Tip 3 : Prepare for the behavioural questions