two_sum

dz / leetcode / two_sum

Node Tree

• URL
• problem
  • cpp_impl
    • subtract_from_target
      • relies_on_exactly_one_answer
    • caching_vs_smaller_inner_loop
    • unordered_map_cpp
  • intuition
    • better_performance
      • better_impl
      • caching_vs_smaller_inner_loop

Nodes

URL
content	URL
hyperlink	https://leetcode.com/problems/two-sum

problem
content	two-sum: given an array of integers =nums= and an integer =target=, return indices of the two numbers such that they add up to =target=. You may assume that each input would have exactly one solution, and may not use the same element twice.
children	cpp_impl, intuition

intuition
content	This can be solved using brute force using two loops. For each number, add it with every other number, and return the pair if it adds up to the target. This yields a performance time of O(n^2).
children	better_performance (follow-up, how to do better performance)
parents	problem

better_performance
content	This can be solved in less than O(n^2) time by realizing that pairs can be in any order. Comparing indices A and B is equivalent to B and A. My gut tells me that this cuts it in half, so O(n^2)/2, but I have yet to prove it.
children	better_impl (how to implement), caching_vs_smaller_inner_loop (I thought about using a smaller inner loop)
parents	intuition

better_impl
content	How to keep track of pairs already done? There's always brute-force of keeping track. But, you can also order the pairs. There is a total ordering here, and you can choose to only consider pairs where A < B. If the outer loop is A, the inner loop is B, the inner loop could iterate up to A.
parents	better_performance

cpp_impl
content	The CPP solutions don't implement the naive n^2 solution and instead use hash maps to cache results to remove the inner loop used for searching, reducing performance from O(n) to O(1).
children	subtract_from_target, caching_vs_smaller_inner_loop (the solutions here use caching via an unordered map), unordered_map_cpp
parents	problem

subtract_from_target
content	There are two implementations, but the gist is to keep track of the target minus the number in the map, the idea being that that key is the only solution for to make that number work. The value stored is the indice. If the matching pair is found, it will be a hit on the map, and the two indices are returned.
children	relies_on_exactly_one_answer
parents	cpp_impl

unordered_map_cpp
content	Uses an unordered map in C++
parents	cpp_impl
remarks	find() and end() methods are used. If find() == end(), it means it is not in there.
hyperlink	https://en.cppreference.com/w/cpp/container/unordered_map

relies_on_exactly_one_answer
content	The problem states there is exactly one answer, which rules out the possibility of accidently returning the same indices.
parents	subtract_from_target

caching_vs_smaller_inner_loop
content	My initial idea was to use a smaller inner loop to remove redundancies in searching for an answer. I referred to caching as a solution that only works if you have the memory for it. I was thinking about a 2d matrix, which is very memory-intensive. The C++ uses a map which is way more clever.
parents	cpp_impl, better_performance