Which of the following offers better overall complexity in terms of both time and space (Java)

a). 2 ArrayDeque structures

or

b). a Single TreeMap ?

Can you provide some guidance on this?

I was trying to solve 1793C - Dora and Search in the Codeforces Round 852 (Div. 2) with both options, I passed all the test cases using a TreeMap, but it seems to have memory size of 15100 KB. Can you guys help in evaluating complexities and suggesting which of them is better?