two_sum
dz / leetcode / two_sumNode Tree
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 | caching_vs_smaller_inner_loop (I thought about using a smaller inner loop), better_impl (how to implement) |
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 | unordered_map_cpp, caching_vs_smaller_inner_loop (the solutions here use caching via an unordered map), subtract_from_target |
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 |