How to use a 'two pointer' algorithm in Elixir

Questions / Help
, ,
1

I’m learning Elixir with Leetcode.

The Leetcode problem is Valid Triangle Number.

My Rust solution uses two pointers with array

impl Solution {
    pub fn triangle_number(mut nums: Vec<i32>) -> i32 {
        nums.sort();
        let mut ans = 0;
        for i in 2..nums.len() {
            let mut left = 0;
            let mut right = i - 1;
            while left < right {
                if nums[left] + nums[right] > nums[i] {
                    ans += right - left;
                    right -= 1;
                } else {
                    left += 1;
                }
            }
        }
        ans as i32
    }
}

I got Timeout when I trying to convert this code to Elixir.

defmodule Solution do
  @spec triangle_number(nums :: [integer]) :: integer
  def triangle_number(nums) do
     len = Enum.count(nums)
     if len < 3 do
        0
     else
        nums |> Enum.sort |> loop_nums(2, len)
     end
  end
  
  def loop_nums(nums, i, len) do
      if i == len do
         0
      else
         check_intervals(nums, 0, i - 1, i) + loop_nums(nums, i + 1, len)
      end
  end
  
  def check_intervals(nums, a, b, c) do
      cond do
          a >= b -> 0
          Enum.at(nums, a) + Enum.at(nums, b) > Enum.at(nums, c) -> b - a + check_intervals(nums, a, b - 1, c)
          true -> check_intervals(nums, a + 1, b, c)
      end 
  end 
end

How to improve the performance?

Thank you.

2

nums is a list, so Enum.at has an O(N) access time. Switching nums to a map:

faster_nums = 
  nums
  |> Enum.sort()
  |> Enum.with_index()
  |> Map.new(fn {value, index} -> {index, value} end)

and using Map.get or the Access protocol:

faster_nums[a]    # instead of Enum.at(nums, a)

should do the trick, although that would be far from perfect. You can consider using Erlang’s array.

4 Likes
3

Thanks for your reply.

I got AC after switch nums to Map.

Should I always use Map to simulate random access to an Array?

4

The best approach would be to come up with an algorithm that works well with immutable data structures. But the reality is that it’s going to be extra work since most of the problems of this kind are designed with the assumption that an array with O(1) random access time is the most basic data structure available in any given language. This is just not true for Elixir since it mostly works with tuples (fixed size, O(1) access) or lists (O(1) prepend and O(N) random access).

Using a map got me through all of Advent of Code exercises, so I think it’s a viable solution. But I would be extra careful trying to push that approach for production-ready systems.

2 Likes
5

Alternatively, you can use a library like Arrays which exposes purely functional arrays which have very good time- and memory-properties, especially for operations such as accessing random elements or modifying random elements.
Depending on the exact array implementation, these run in an amortized O(log10(n)) or O(log32(n)). The difference between this and ‘true’ O(1) is only noticeable at ridiculously large collection sizes (at which point the array will no longer fit in your cache, or possibly in all of your non-swap RAM, which will probably overshadow these differences anyway.)

Of course an implementation in a ‘close to the metal’ language will be even faster and even more predictable (like no GC pauses), but for most situations this difference in efficiency is not worth dwelling on too long, as it is much more likely that your app will be bottlenecked by other things (like e.g. reading from/to files or communicating with external services over a network)
And for programming exercises such as Leetcode, these approaches are most definitely more than fast enough :slight_smile: .

3 Likes