leetcode/3sum

3sum

dz / leetcode / 3sum

Summary

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 enumerate_all_unique_pairs_and_ideal_solution, any_way_to_remove_values, intuition_post_hint

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 hash_table_intuition_vs_reality (intuition), hash_table_solution (along the lines of what I was thinking about), intuition_post_hint (looks pretty close, though it's a bit clunky after looking at hint)
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 enumerate_all_unique_pairs_and_ideal_solution, intuition

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 hash_table_intuition_vs_reality (reality), mathematical_set (treats hash table like set data structure)
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 enumerate_all_unique_pairs_and_ideal_solution, hash_table_solution

mathematical_set
parents hash_table_solution
hyperlink https://en.wikipedia.org/wiki/Set_(mathematics)