3sum
dz / leetcode / 3sumSummary
15. 3sum. Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.
Node Tree
Nodes
URL | |
content | URL |
hyperlink | https://leetcode.com/problems/3sum/ |
intuition | |
content | The thing that makes this problem interesting is that the triplet combinations are distinct. You can't simply brute force all the combinations, you actually need a way to keep track of values. |
children | intuition_post_hint, any_way_to_remove_values, enumerate_all_unique_pairs_and_ideal_solution |
intuition_brute_force | |
content | Go through all the combinations and test for 0. When a match has been found, the triplet values are sorted and then stored in a 3d hashmap. If an entry doesn't exist yet, append it to the array and the map, otherwise ignore. This is O(n^3) performance time, so not great. |
any_way_to_remove_values | |
content | I wonder if there's any way to remove values from the input array. Indices aren't really considered, only the values themselves. |
parents | intuition |
enumerate_all_unique_pairs_and_ideal_solution | |
content | Similar to some of the two-sum solutions, use a hashmap to store all unique pairs with their ideal third pair match as the key, and a tuple containing the other two values. Building up the hashmap would take O(n^2), and the lookup would take O(n) time. You'd need a way to prevent duplicate lookups, which can be done with another map, or by removing the key from the map. |
children | intuition_post_hint (looks pretty close, though it's a bit clunky after looking at hint), hash_table_intuition_vs_reality (intuition), hash_table_solution (along the lines of what I was thinking about) |
parents | intuition |
intuition_post_hint | |
content | It seems like some kind of hashmap is warranted to speed things up. I think my solution could work, but it feels clunky to have what is essentially two hash maps (one to store answers, one two keep track of found solutions). I think I am missing something. |
parents | intuition, enumerate_all_unique_pairs_and_ideal_solution |
cpp_impl | |
content | C++ implementation (couldn't find editorial anywhere) |
parents | wikipedia |
sort_array_first | |
content | array is sorted first. This seems to make a lot of things easier, including the duplication issue. |
wikipedia | |
content | wikipedia article on 3sum, including pseudo-code for the canonical solution in O(n^2) time. |
children | comparison_based_model, cpp_impl (main C++ implementation uses this), hash_table_solution |
hyperlink | https://en.wikipedia.org/wiki/3SUM |
comparison_based_model | |
content | A comparison based model uses pre-sorting of the list and then tests all possible pairs in a careful order that prevents the need to binary search for the pairs in a sorted list, causing O(n^2) time. |
parents | wikipedia |
hash_table_solution | |
content | For an input array S[0..n-1], insert S(i) into a hash table, and then, for each index i and j, checking whether the hash table contains the integer -(S[i] + S[j]). |
children | mathematical_set (treats hash table like set data structure), hash_table_intuition_vs_reality (reality) |
parents | enumerate_all_unique_pairs_and_ideal_solution, wikipedia |
hash_table_intuition_vs_reality | |
content | My intuitive solution involved computing the ideal last value in the triplet and having that be the key, and a tuple be the values. Meanwhile, the actual solution uses the hash map as more of a mathematical set operation, where the "last value" is imply the negative, of the other two values. A check is seeing if the value belongs to the set. |
parents | hash_table_solution, enumerate_all_unique_pairs_and_ideal_solution |
mathematical_set | |
parents | hash_table_solution |
hyperlink | https://en.wikipedia.org/wiki/Set_(mathematics) |