Intersection of Three Sorted Arrays

🏠 ⬅️ ➡️

Given three integer arrays arr1, arr2 and arr3 sorted in strictly increasing order, return a sorted array of only the integers that appeared in all three arrays.

Example 1:

Input: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8] Output: [1,5] Explanation: Only 1 and 5 appeared in the three arrays.

Example 2:

Input: arr1 = [197,418,523,876,1356], arr2 = [501,880,1593,1710,1870], arr3 = [521,682,1337,1395,1764] Output: []

Constraints:

  • 1 <= arr1.length, arr2.length, arr3.length <= 1000
  • 1 <= arr1[i], arr2[i], arr3[i] <= 2000
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 = 5
    integer, dimension(n) :: arr1, arr2, arr3
    integer, dimension(:), allocatable :: result
    integer :: i, j, k

    ! Example 1
    arr1 = [1, 2, 3, 4, 5]
    arr2 = [1, 2, 5, 7, 9]
    arr3 = [1, 3, 4, 5, 8]
    call solve(arr1, arr2, arr3, result)
    write (unit=error_unit, fmt='(*(I0, 1X))') result

    ! Example 2
    arr1 = [197, 418, 523, 876, 1356]
    arr2 = [501, 880, 1593, 1710, 1870]
    arr3 = [521, 682, 1337, 1395, 1764]
    call solve(arr1, arr2, arr3, result)
    write (unit=error_unit, fmt='(*(I0, 1X))') result

contains

    subroutine solve(arr1, arr2, arr3, result)
        implicit none
        integer, dimension(:), intent(in) :: arr1
        integer, dimension(:), intent(in) :: arr2
        integer, dimension(:), intent(in) :: arr3
        integer, dimension(:), allocatable, intent(out) :: result
        integer :: i, j, k

        allocate (result(size(arr1)))

        i = 1
        j = 1
        k = 1
        do while (i <= size(arr1) .and. j <= size(arr2) .and. k <= size(arr3))
            if (arr1(i) == arr2(j) .and. arr1(i) == arr3(k)) then
                result(i) = arr1(i)
                i = i + 1
                j = j + 1
                k = k + 1
            else if (arr1(i) < arr2(j)) then
                i = i + 1
            else if (arr1(i) > arr3(k)) then
                k = k + 1
            else
                stop "Error: unexpected condition"
            end if
        end do

        result = result(1:i-1)
    end subroutine solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module main

implicit none

integer, parameter :: n = 1000
integer :: i, j, k
integer :: arr1(n), arr2(n), arr3(n)
integer :: result(n)

! read input
read (*, *) arr1
read (*, *) arr2
read (*, *) arr3

! initialize result array
result = 0

! loop through each element in arr1
do i = 1, size(arr1)
    ! check if element is in arr2 and arr3
    if (binary_search(arr2, arr1(i)) .and. binary_search(arr3, arr1(i))) then
        ! if element is in both arr2 and arr3, add it to result
        result(i) = arr1(i)
    end if
end do

! sort result array
call sort(result)

! print output
do i = 1, size(result)
    write (*, *) result(i)
end do

contains

! binary search function
function binary_search(arr, x) result(found)
    integer, intent(in) :: arr(:)
    integer, intent(in) :: x
    logical :: found
    integer :: low, high, mid

    low = 1
    high = size(arr)

    do while (low <= high)
        mid = (low + high) / 2
        if (arr(mid) == x) then
            found = .true.
            return
        else if (arr(mid) < x) then
            low = mid + 1
        else
            high = mid - 1
        end if
    end do

    found = .false.
end function binary_search

! sort function
subroutine sort(arr)
    integer, intent(inout) :: arr(:)
    integer :: i, j, temp

    do i = 1, size(arr) - 1
        do j = i + 1, size(arr)
            if (arr(i) > arr(j)) then
                temp = arr(i)
                arr(i) = arr(j)
                arr(j) = temp
            end if
        end do
    end do
end subroutine sort

end module main

! test cases
program test_cases
    use main
    implicit none

    integer, parameter :: n = 5
    integer :: arr1(n), arr2(n), arr3(n)

    ! example 1
    arr1 = [1, 2, 3, 4, 5]
    arr2 = [1, 2, 5, 7, 9]
    arr3 = [1, 3, 4, 5, 8]
    call solve(arr1, arr2, arr3)

    ! example 2
    arr1 = [197, 418, 523, 876, 1356]
    arr2 = [501, 880, 1593, 1710, 1870]
    arr3 = [521, 682, 1337, 1395, 1764]
    call solve(arr1, arr2, arr3)
end program test_cases
🌐 Data from online sources 
def arraysIntersection(arr1, arr2, arr3):
    i, j, k = 0, 0, 0
    result = []
    while i < len(arr1) and j < len(arr2) and k < len(arr3):
        if arr1[i] == arr2[j] and arr2[j] == arr3[k]:
            result.append(arr1[i])
            i, j, k = i + 1, j + 1, k + 1
        else:
            if arr1[i] <= arr2[j] and arr1[i] <= arr3[k]:
                i += 1
            elif arr2[j] <= arr3[k]:
                j += 1
            else:
                k += 1
    return result

The algorithm for finding the intersection of three sorted integer arrays follows these steps:

  1. Initialize three pointers, each pointing to the starting index of the three input arrays arr1, arr2, and arr3.
  2. Create an empty result array result to store the values found in the intersection.
  3. Use a while loop that continues as long as none of the pointers reach the end of their respective arrays.
  4. Inside the loop, compare the values pointed by the three pointers.
  5. If all three values are the same, add the value to the result array and move all three pointers forward by 1.
  6. If the values are not the same, find the minimum of the three values and move the pointer pointing to the minimum value forward by 1.
  7. When the loop ends and any of the pointers have reached the end of their respective arrays, the algorithm is terminated, and the result array is returned.

This algorithm has a time complexity of O(n), where n is the length of the input arrays since it only iterates once through the arrays. The space complexity is O(m) where m is the number of elements in the intersection.

🌐 Data from online sources 
#include <vector>
using namespace std;

vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
    int i = 0, j = 0, k = 0;
    vector<int> result;
    while (i < arr1.size() && j < arr2.size() && k < arr3.size()) {
        if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) {
            result.push_back(arr1[i]);
            i++; j++; k++;
        } else {
            if (arr1[i] <= arr2[j] && arr1[i] <= arr3[k]) i++;
            else if (arr2[j] <= arr3[k]) j++;
            else k++;
        }
    }
    return result;
}

The algorithm for finding the intersection of three sorted integer arrays follows these steps:

  1. Initialize three pointers, each pointing to the starting index of the three input arrays arr1, arr2, and arr3.
  2. Create an empty result array result to store the values found in the intersection.
  3. Use a while loop that continues as long as none of the pointers reach the end of their respective arrays.
  4. Inside the loop, compare the values pointed by the three pointers.
  5. If all three values are the same, add the value to the result array and move all three pointers forward by 1.
  6. If the values are not the same, find the minimum of the three values and move the pointer pointing to the minimum value forward by 1.
  7. When the loop ends and any of the pointers have reached the end of their respective arrays, the algorithm is terminated, and the result array is returned.

This algorithm has a time complexity of O(n), where n is the length of the input arrays since it only iterates once through the arrays. The space complexity is O(m) where m is the number of elements in the intersection.