# Intersect of 2 arrays

**URL:** <https://discourse.julialang.org/t/intersect-of-2-arrays/53387>\
**Category:** New to Julia\
**Created:** [January 15, 2021, 3:19pm UTC](https://discourse.julialang.org/t/intersect-of-2-arrays/53387 "2021-01-15T15:19:26Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![Laco\_Kovac](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/laco_kovac/32/20684_2.png) [@Laco\_Kovac](https://discourse.julialang.org/u/Laco_Kovac)\
**Post date:** [January 15, 2021, 3:19pm UTC](https://discourse.julialang.org/t/intersect-of-2-arrays/53387/1 "2021-01-15T15:19:26Z")

</div>

I have 2 arrays of Dict containing from and to items, both of type ZonedDateTime (although for our example they could be integers, doesn’t matter). They are basically 2 arrays of ranges.

What would be the simplest/the most efficient way to determine whether they intersect?

Thank you,

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [January 15, 2021, 3:27pm UTC](https://discourse.julialang.org/t/intersect-of-2-arrays/53387/2 "2021-01-15T15:27:50Z")

</div>

Intersect in which sense? Have the same keys? Have the same values? Have the same pairs of key and value? The intersection is about the Dicts having the same keys/values, or the keys/values itself intersecting with the keys/values of another Dict?

---

<div class="post-metadata">

**Author:** ![Skoffer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/skoffer/32/378_2.png) [@Skoffer](https://discourse.julialang.org/u/Skoffer)\
**Post date:** [January 15, 2021, 4:08pm UTC](https://discourse.julialang.org/t/intersect-of-2-arrays/53387/3 "2021-01-15T16:08:30Z")

</div>

Can you provide an [MWE](https://discourse.julialang.org/t/psa-make-it-easier-to-help-you/14757), please? It would be much easier if you give a small example of what you have and what you are trying to achieve.

---

<div class="post-metadata">

**Author:** ![Laco\_Kovac](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/laco_kovac/32/20684_2.png) [@Laco\_Kovac](https://discourse.julialang.org/u/Laco_Kovac)\
**Post date:** [January 15, 2021, 4:09pm UTC](https://discourse.julialang.org/t/intersect-of-2-arrays/53387/4 "2021-01-15T16:09:46Z")

</div>

Let’s assume “from” and “to” are integers (so that’s easier for me to write an example).

A = [Dict(“from”=\>1, “to”=\>20), Dict(“from”=\>51, “to”=\>100)]  
B = [Dict(“from”=\>21, “to”=\>50), Dict(“from”=\>99, “to”=\>105)]

In this case, they do intersect with 2 values, 99 and 100.

In another example:

C = [Dict(“from”=\>1, “to”=\>20), Dict(“from”=\>51, “to”=\>100)]  
D = [Dict(“from”=\>21, “to”=\>50), Dict(“from”=\>101, “to”=\>125)]

They don’t intersect.

Thank you.

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [January 15, 2021, 7:08pm UTC](https://discourse.julialang.org/t/intersect-of-2-arrays/53387/5 "2021-01-15T19:08:06Z")

</div>

Why are you using `Dict`s for the ranges? Why not use `UnitRange{Int64}` (or in your real case `UnitRange{ZonedDateTime}`).

The ranges inside the same array are mutually exclusive (i.e., do not share any numbers?) the arrays are sorted? All of this is relevant for knowing what is the most efficient algorithm. If the answer to both is “yes”, then the code below should suffice.

```julia
A = [1:20, 51:100]
B = [21:50, 99:105]
C = [1:20, 51:100]
D = [21:50, 101:125]

function list_intersections(A, B)
    idx_a, idx_b = 1, 1
    len_a, len_b = length.((a, b)) 
    intersects = UnitRange{Int64}[]
    while idx_a <= len_a && idx_b <= b
        if last(A[idx_a]) < first(B[idx_b])
            idx_a += 1
        elseif last(B[idx_b]) < first(A[idx_a])
            idx_b += 1
        else
            r = intersect(A[idx_a], B[idx_b])
            !isempty(r) && push!(intersects, r)
            if last(A[idx_a]) < last(B[idx_b])
                idx_a += 1
            else
                idx_b += 1
            end 
        end
    end   
    return intersects
end

list_intersections(A, B)
list_intersections(C, D)

```

Gives the expected results.

---

<div class="post-metadata">

**Author:** ![Skoffer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/skoffer/32/378_2.png) [@Skoffer](https://discourse.julialang.org/u/Skoffer)\
**Post date:** [January 15, 2021, 7:17pm UTC](https://discourse.julialang.org/t/intersect-of-2-arrays/53387/6 "2021-01-15T19:17:06Z")

</div>

If you can do not mind use other structures than `Dict` (which is rather inefficient in this case), you can use nice [Intervals.jl](https://github.com/invenia/Intervals.jl) package. Something like this

```julia
function combineintervals(A, B)
    res = Vector{eltype(A)}()
    for a in A, b in B
        c = intersect(a, b)
        isempty(c) || push!(res, c)
    end
    return res
end

A = [1..20, 51..100]
B = [21..50, 101..125]

julia> combineintervals(A, B)
Interval{Int64, Closed, Closed}[]

julia> combineintervals(A, [21..50, 99..125])
1-element Vector{Interval{Int64, Closed, Closed}}:
 Interval{Int64, Closed, Closed}(99, 100)

```

Using this package makes sense also if you are working with seconds resolution, since you can use for example `close, open` intervals, for example

```julia
using Dates

julia> Interval{Closed, Open}(DateTime("2021-01-01"), DateTime("2021-02-01"))
Interval{DateTime, Closed, Open}(DateTime("2021-01-01T00:00:00"), DateTime("2021-02-01T00:00:00"
))

```

and still be able to get correct results without worrying of edge cases.

---

<div class="post-metadata">

**Author:** ![cchderrick](https://avatars.discourse-cdn.com/v4/letter/c/ecd19e/32.png) [@cchderrick](https://discourse.julialang.org/u/cchderrick)\
**Post date:** [January 15, 2021, 9:22pm UTC](https://discourse.julialang.org/t/intersect-of-2-arrays/53387/7 "2021-01-15T21:22:40Z")

</div>

I had some time at lunch; and always nice to learn never-heard packages like Intervals.

```julia
struct FromTo
    from
    to
    function FromTo(f,t)
        @assert t>=f "`To` has to be >= `From`"
        new(f,t)
    end
end

struct FromToCollections
    l::Array{FromTo}
end

A = FromToCollections([FromTo(1,20),FromTo(51,100)])
B = FromToCollections([FromTo(21,50),FromTo(99,105)])
C = FromToCollections([FromTo(1,20), FromTo(51, 100)])
D = FromToCollections([FromTo(21, 50), FromTo(101,125)])

function intersect(A::FromTo, B::FromTo)
    # The complement case seems to be easier to define
    return !((A.to < B.from) ||(B.to < A.from))
end

function intersect(As::FromToCollections, Bs::FromToCollections)
    for a in As.l, b in Bs.l
        intersect(a,b) && return true
    end
    return false
end

```

```julia-repl
julia> intersect(A,B)
true

julia> intersect(C,D)
false

```

Generally I like to define my own type, then I can defined what I meant `intersect` for my own type at a very unclutter way, and build my way up.

Edit:  
on a second thought, probably should use a different name for intersect since it return “are they intersect” and doesn’t return “the intersect”.

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [January 15, 2021, 10:00pm UTC](https://discourse.julialang.org/t/intersect-of-2-arrays/53387/8 "2021-01-15T22:00:31Z")

</div>

Also, `intersect` is already defined by `Base` because `Base` already has `UnitRange`s.

Sincerely, unless there is a good reason, this seems to be reinventing the wheel. Often an interval is just two values that have ordering functions defined for them, and there is a lot of code that already works over both `UnitRange` and the types of `Intervals.jl` (that also support the concept of closed and open ranges).