I am new to learning data structures and algorithms and am starting NeetCode 150 problems. The first problem I encountered was not difficult, I understand why it works, but I am curious to why the best solution involves the use of a HashSet instead of an array.

I’m sure it comes back to time complexity which is a topic I am struggling a bit to grasp, so I am hoping someone can give me a simple breakdown as to why one solution is better than the other, and if it would be really bad to use an array here instead of a HashSet (if I used it in an interview would they not like it).

This is the solution I came up with. It is almost identical other than the use of arrays and .append() instead of HashSet’s and .add(). The solution was technically correct but based on the research I did the HashSet solution appears to better/faster, and I would like some help understanding why.

class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        newArray = []
        for i in nums:
            if i in newArray:
                return True
            newArray.append(i)    
        return False

Here is the actual best solution.

class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        hashset = set()

        for n in nums:
            if n in hashset:
                return True
            hashset.add(n)
        return False

What are the differences? Also what impact would adding nums.sort() have on the first approach? Would that alter the run time in any way? Sorry if these questions are painfully obvious I just need some help wrapping me head around the concepts.