Leetcode 18: 4 sum

leetcode_18_four_sum.rb

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`.


```