Last active
March 30, 2024 05:59
-
-
Save codertcet111/16142e989092f79d08ffc897b388ed7c to your computer and use it in GitHub Desktop.
Leetcode 18: 4 sum
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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`. | |
``` |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment