The problem

Link to the problem

Brute force solution

Runtime O(n²)

Spacetime O(1)

The obvious brute force solution is just check every combination with two pointers. Since the array is unordered, the worst-case scenario is if the answer is the final pair. This results in a runtime of O(n²) and a spacetime of O(1) for the two pointers.

The trick: Some fun math and hashmaps

The trick here is noticing that we're given a target. Previously, for the brute force solution, we were using the following formula to search for two unknown variables, hoping that they would add up to our target.

• target = nums[L] + nums[R]

If we rewrite the formula, we can take the difference at the current known index. Doing this for all the elements gives us a list of matching complements, one of which is the answer we're looking for.

• difference = target - nums[i]

Given that we're guaranteed a single unique solution from the constraints, we can find the solution in two passes.

In the first pass, we calculate the complement for every element we visit. In the second pass, we use these complements to locate the matching pair.

Storing the differences in a HashMap, {difference, index}, allows us to compare the complements at an O(1) runtime for a spacetime tradeoff of O(n).

Once we find the matching complement during our second pass, just return the current index and the matching HashMap value, which stores the other index.

Final evaluation

Runtime O(n)

Spacetime O(n)