Leetcode 18: 4 sum hard # def four_sum(nums, target) # nums.sort! # set = Set.new # output = [] # (0..nums.length - 4).each do |i| # (i + 1..nums.length - 3).each do |j| # new_target = target - nums[i] - nums[j] # low = j + 1 # high = nums.length - 1 # while low < high # if nums[low] + nums[high] < new_target # low += 1 # elsif nums[low] + nums[high] > new_target # high -= 1 # else # set.add([nums[i], nums[j], nums[low], nums[high]]) # low += 1 # high -= 1 # end # end # end # end # output = set.to_a # return output # end def max_four(nums) # nums.tally.select{|k,v| v<= 4}.keys.to_a count = nums.tally arr = [] count.each do |k,v| ([v,4].min).times { arr << k } end arr end def four_sum(nums, target) nums = max_four(nums) res = Set[] #hash: sum is key, array of pairs of indices is value two_sum = Hash.new { |h,k| h[k] = [] } (0...nums.length).each do |a| (a+1...nums.length).each do |b| sum = nums[a] + nums[b] two_sum[target - sum].each do |pair| if ([a,b] + pair).uniq.length == 4 c,d = pair res.add([nums[a],nums[b],nums[c],nums[d]].sort) end end two_sum[sum] << [a,b] end end res.to_a end ``` Explanation Sure, let's break down the code with an example using `nums = [1, 0, -1, 0, -2, 2]` and `target = 0`. 1. **Initialize Hash Map for Two Sums**: ```ruby two_sum = Hash.new { |h, k| h[k] = [] } ``` This line initializes a hash map `two_sum` where the keys represent the possible sums of pairs of elements from `nums`, and the values are arrays containing pairs of indices that produce the respective sums. 2. **Iterate Over Pairs of Indices**: ```ruby (0...nums.length).each do |a| (a+1...nums.length).each do |b| ``` These nested loops iterate over all pairs of indices `(a, b)` in the `nums` array. 3. **Calculate Sum and Check Complementary Value**: ```ruby sum = nums[a] + nums[b] two_sum[target - sum].each do |pair| ``` For each pair of indices `(a, b)`, it calculates the sum of the corresponding elements (`nums[a] + nums[b]`). Then, it looks for the complementary value (`target - sum`) in the `two_sum` hash map. If there are pairs of indices stored for that complementary sum, it proceeds to the next step. 4. **Check if Quadruplet is Unique**: ```ruby if ([a, b] + pair).uniq.length == 4 ``` It checks if the indices `[a, b]` combined with the indices `pair` form a unique quadruplet. If they do (i.e., all four indices are distinct), it proceeds to the next step. 5. **Add Quadruplet to Result Set**: ```ruby c, d = pair res.add([nums[a], nums[b], nums[c], nums[d]].sort) ``` It extracts the indices `c` and `d` from the pair, then adds the quadruplet `[nums[a], nums[b], nums[c], nums[d]]` to the result set `res`. The quadruplet is sorted to ensure consistency. 6. **Update Hash Map with Current Pair**: ```ruby two_sum[sum] << [a, b] ``` Finally, it updates the `two_sum` hash map with the current pair of indices `[a, b]`, associating them with the sum `sum`. This process continues for all pairs of indices in the `nums` array. After processing all possible pairs, the algorithm returns the unique quadruplets found in the result set `res`. ```