# How to use a 'two pointer' algorithm in Elixir

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.

`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

I got AC after switch nums to Map.

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

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

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 .

3 Likes