I’d use a set and iterate over the list and for each element I’d check if the set contains that element and if it does, it means we found a positive answer and if not, add k - arr[i] to the set.

2 elements: we will do a contains() on a set with 0 elements, then an add(), then a contains() on a set with 1 element, then an add().

3 elements: all of the above, plus a contains() on a set with 2 elements, then an add()

Assuming we skip the last add() when we know we've reached the end of the list, worst-case would be calling contains() on N sets of length 0 through N-1, plus calling add()N-1 times.

This is definitely less space-efficient than my solution, because of the set, but is it more time-efficient? What do you think?

I think it depends on how set works under the hood.
At first, because there is only one for loop, one might think it’s only O(n).

But how does the `contains()’ method actually work? I have just read here and it says that set will internally iterate its elements and compare each element to the object passed as parameter.

Another way of making sure that there isn’t another for loop going on behind the scenes is by using a map. Because accessing an item requires O(1) time.(as far as I know)

## re: Java Daily Coding Problem #001 VIEW POST

FULL DISCUSSIONI’d use a set and iterate over the list and for each element I’d check if the set contains that element and if it does, it means we found a positive answer and if not, add

`k - arr[i]`

to the set.Thank you for sharing!

I thought the same and this is way more efficient runtime.

Very clever! I like this answer.

What is the Big-O of this solution, though?

In the worst case, if we have...

2 elements:we will do a`contains()`

on a set with 0 elements, then an`add()`

, then a`contains()`

on a set with 1 element, then an`add()`

.3 elements:all of the above, plus a`contains()`

on a set with 2 elements, then an`add()`

Assuming we skip the last

`add()`

when we know we've reached the end of the list, worst-case would be calling`contains()`

on`N`

sets of length 0 through`N-1`

, plus calling`add()`

`N-1`

times.This is definitely less space-efficient than my solution, because of the set, but is it more time-efficient? What do you think?

I think it depends on how set works under the hood.

At first, because there is only one for loop, one might think it’s only

`O(n)`

.But how does the `contains()’ method actually work? I have just read here and it says that set will internally iterate its elements and compare each element to the object passed as parameter.

Another way of making sure that there isn’t another for loop going on behind the scenes is by using a

`map`

. Because accessing an item requires`O(1)`

time.(as far as I know)So it could be that the

`Set`

solution is just as memory-efficient as the double-`for`

loop. I'd love to do a benchmark of this.If you do, please let me know what the results are!

Thanks!

yo!🔥