Merge Similar Items

🏠 ⬅️ ➡️

You are given two 2D integer arrays, items1 and items2, representing two sets of items. Each array items has the following properties:

  • items[i] = [valuei, weighti] where valuei represents the value and weighti represents the weight of the ith item.
  • The value of each item in items is unique.

Return a 2D integer array ret where ret[i] = [valuei, weighti], with weighti being the sum of weights of all items with value valuei.

Note: ret should be returned in ascending order by value.

Example 1:

Input: items1 = [[1,1],[4,5],[3,8]], items2 = [[3,1],[1,5]] Output: [[1,6],[3,9],[4,5]] Explanation: The item with value = 1 occurs in items1 with weight = 1 and in items2 with weight = 5, total weight = 1 + 5 = 6. The item with value = 3 occurs in items1 with weight = 8 and in items2 with weight = 1, total weight = 8 + 1 = 9. The item with value = 4 occurs in items1 with weight = 5, total weight = 5.
Therefore, we return [[1,6],[3,9],[4,5]].

Example 2:

Input: items1 = [[1,1],[3,2],[2,3]], items2 = [[2,1],[3,2],[1,3]] Output: [[1,4],[2,4],[3,4]] Explanation: The item with value = 1 occurs in items1 with weight = 1 and in items2 with weight = 3, total weight = 1 + 3 = 4. The item with value = 2 occurs in items1 with weight = 3 and in items2 with weight = 1, total weight = 3 + 1 = 4. The item with value = 3 occurs in items1 with weight = 2 and in items2 with weight = 2, total weight = 2 + 2 = 4. Therefore, we return [[1,4],[2,4],[3,4]].

Example 3:

Input: items1 = [[1,3],[2,2]], items2 = [[7,1],[2,2],[1,4]] Output: [[1,7],[2,4],[7,1]] Explanation: The item with value = 1 occurs in items1 with weight = 3 and in items2 with weight = 4, total weight = 3 + 4 = 7. The item with value = 2 occurs in items1 with weight = 2 and in items2 with weight = 2, total weight = 2 + 2 = 4. The item with value = 7 occurs in items2 with weight = 1, total weight = 1. Therefore, we return [[1,7],[2,4],[7,1]].

Constraints:

  • 1 <= items1.length, items2.length <= 1000
  • items1[i].length == items2[i].length == 2
  • 1 <= valuei, weighti <= 1000
  • Each valuei in items1 is unique.
  • Each valuei in items2 is unique.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    use, intrinsic :: iso_fortran_env, only : error_unit, DP => REAL64
    implicit none
    integer, parameter :: n = 3
    integer, dimension(n, 2) :: items1 = reshape([1,1,4,5,3,8],[n,2])
    integer, dimension(n, 2) :: items2 = reshape([3,1,1,5],[n,2])
    integer, dimension(:, :), allocatable :: ret

    allocate(ret(n, 2))

    call solve(items1, items2, ret)

    write (unit=error_unit, fmt='(*(I0, 1X))') ret

contains

    subroutine solve(items1, items2, ret)
        implicit none
        integer, intent(in) :: items1(:, :)
        integer, intent(in) :: items2(:, :)
        integer, intent(out) :: ret(:, :)
        integer :: i, j, k
        integer :: sum_weights

        do i = 1, size(items1, 1)
            do j = 1, size(items2, 1)
                if (items1(i, 1) == items2(j, 1)) then
                    sum_weights = items1(i, 2) + items2(j, 2)
                    do k = 1, size(ret, 1)
                        if (ret(k, 1) == items1(i, 1)) then
                            ret(k, 2) = sum_weights
                            exit
                        end if
                    end do
                end if
            end do
        end do

        ! sort ret by value
        call sort(ret, 1)

    end subroutine solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module main

implicit none

integer, parameter :: dp = selected_real_kind(15, 307)

integer, intent(in) :: items1(:, :)
integer, intent(in) :: items2(:, :)
integer :: ret(size(items1, 1), 2)

integer :: i, j, k, l, m
integer :: value, weight

! Initialize the ret array with the values and weights of items1
do i = 1, size(items1, 1)
    ret(i, 1) = items1(i, 1)
    ret(i, 2) = items1(i, 2)
end do

! Sort the ret array in ascending order by value
call sort(ret, 1, size(ret, 1), 2, order='ascending')

! Loop through items2 and add the weights of items with the same value as in items1
do i = 1, size(items2, 1)
    value = items2(i, 1)
    weight = items2(i, 2)

    ! Find the index of the first item with the same value as in items2
    do j = 1, size(ret, 1)
        if (ret(j, 1) == value) exit
    end do

    ! Add the weight of items with the same value as in items2
    do k = j, size(ret, 1)
        if (ret(k, 1) /= value) exit
        ret(k, 2) = ret(k, 2) + weight
    end do
end do

! Print the result
do i = 1, size(ret, 1)
    write (*, '(i5, x, i5)') ret(i, 1), ret(i, 2)
end do

contains

subroutine sort(array, low, high, dim, order)
implicit none

integer, intent(inout) :: array(:, :)
integer, intent(in) :: low, high, dim
character(len=*), intent(in) :: order

integer :: i, j, temp

if (low < high) then
    ! Partition the array
    i = low - 1
    j = high + 1
    do
        do while (array(low, dim) < array(j, dim))
            j = j - 1
        end do
        do while (array(i, dim) > array(low, dim))
            i = i + 1
        end do
        if (i < j) then
            do l = 1, dim - 1
                temp = array(i, l)
                array(i, l) = array(j, l)
                array(j, l) = temp
            end do
            do l = 1, 2
                temp = array(i, l)
                array(i, l) = array(j, l)
                array(j, l) = temp
            end do
            i = i + 1
            j = j - 1
        else
            exit
        end if
    end do

    ! Recursively sort the partitions
    call sort(array, low, j, dim, order)
    call sort(array, i, high, dim, order)
end if

end subroutine sort

end module main

program test
use main
implicit none

integer, parameter :: items1(3, 2) = reshape([1, 1, 4, 5, 3, 8], shape(items1))
integer, parameter :: items2(2, 2) = reshape([3, 1, 1, 5], shape(items2))

integer :: ret(size(items1, 1), 2)

call solve(items1, items2, ret)

end program test
🌐 Data from online sources 
def sum_weights(items1, items2):
    weight_sums = {}
    result = []

    for value, weight in items1:
        weight_sums[value] = weight_sums.get(value, 0) + weight
    for value, weight in items2:
        weight_sums[value] = weight_sums.get(value, 0) + weight

    for value, weight in sorted(weight_sums.items()):
        result.append([value, weight])

    return result
  1. Create a map called weightSums to store the sum of weights for every value. Initialize an empty list result for returning the solution.
  2. Iterate over the items1 and items2 arrays. For each [value, weight] pair, add the weight to the weightSums map for that value. If the value is not present in the map, set its value to be equal to the current weight.
  3. Loop through the sorted weightSums items (by key/values in ascending order), and append each [value, weight] to the result list.
  4. Return the result list.
🌐 Data from online sources 
#include <vector>
#include <map>
using namespace std;

vector<vector<int>> sumWeights(vector<vector<int>>& items1, vector<vector<int>>& items2) {
    map<int, int> weightSums;
    vector<vector<int>> result;

    for (const auto& item : items1) {
        weightSums[item[0]] += item[1];
    }
    for (const auto& item : items2) {
        weightSums[item[0]] += item[1];
    }

    for (const auto& entry : weightSums) {
        result.push_back({entry.first, entry.second});
    }

    return result;
}
  1. Create a map called weightSums to store the sum of weights for every value. Initialize an empty list result for returning the solution.
  2. Iterate over the items1 and items2 arrays. For each [value, weight] pair, add the weight to the weightSums map for that value. If the value is not present in the map, set its value to be equal to the current weight.
  3. Loop through the sorted weightSums items (by key/values in ascending order), and append each [value, weight] to the result list.
  4. Return the result list.