LeetCode 835 Image Overlap Elixir solution

LeetCode problem link: 835. Image Overlap

You can find the problem description and solutions in C++, Java, JS, TS and Python programming languages supported by LeetCode here

LeetCode 835. Image Overlap: short Elixir description of the solution

In Elixir solution we use the Translation Vector Counting pattern, the same approach as the C++ solution.
First, we collect the coordinates of all 1s from both images using Enum.with_index and a for comprehension.
For every 1 in img1, we compare it with every 1 in img2 and calculate the translation vector (dx, dy).
If several pairs produce the same translation vector, those 1s will overlap after applying that translation.
We encode (dx, dy) into a single key and use a Map to count how many times each translation occurs.
Because Elixir data structures are immutable, Map.put returns an updated map instead of modifying the existing map in place.
Enum.reduce carries both the frequency map and the current maximum overlap through the iterations.
Let k1 be the number of cells equal to 1 in img1, and k2 be the number of cells equal to 1 in img2.
In this case, if k1 and k2 are the numbers of 1s in the two images, the time complexity is O(n2 + k1 * k2), or O(n4) in the worst case.
Since n <= 30, the worst case is at most 304 = 810,000 pair comparisons, which is acceptable for this problem.
The space complexity is O(n2) because there are only (2n - 1)4 possible translation vectors.

Time complexity: O(n2 + k1 * k2)
Space complexity: O(n2)

In worst case:

Time complexity: O(n4)
Space complexity: O(n2)

LeetCode 835. Image Overlap: Elixir solution

defmodule Solution do
  @spec largest_overlap(img1 :: [[integer]], img2 :: [[integer]]) :: integer
  def largest_overlap(img1, img2) do
    n = length(img1)

    ones1 = collect_ones(img1)
    ones2 = collect_ones(img2)

    size = 2 * n - 1

    {_count, result} =
      Enum.reduce(ones1, {%{}, 0}, fn {r1, c1}, {count, result} ->
        Enum.reduce(ones2, {count, result}, fn {r2, c2}, {count, result} ->
          dx = r2 - r1 + n - 1
          dy = c2 - c1 + n - 1

          key = dx * size + dy

          frequency = Map.get(count, key, 0) + 1

          {
            Map.put(count, key, frequency),
            max(result, frequency)
          }
        end)
      end)

    result
  end

  defp collect_ones(image) do
    for {row, r} <- Enum.with_index(image),
        {1, c} <- Enum.with_index(row),
        do: {r, c}
  end
end