217. Contains Duplicate¶
The objective of this problem is following:
Given an integer array nums
, return true
if any value appears at least twice in the array, and return false
if every element is distinct.
Example 1:
Basically my approach was again a Big O(n²)
which eventually at one test case got time exceeded. But I would still like to showcase on how I approach this problem.
- Since we have to check whether an array contains a duplicate value we would need to check it
n
times whenn
our length of an array is. - So I create a variable with the length of the array minus one to get the actual length. A second variable
counter
which is the length of the array without the minus one. - Now we want to check all items which each other, so I created a while loop which has the condition to run so long until my
counter
is greater or equal to 0. Inside the while loop I have a for loop and in this for loop I created atemp
variable which is set to the last element of the array. - Last but not least I created within the for loop an if condition which checks if the last item of the loop is equal to one of the others.
- When the for loop finish I subtract 1 from the index of my
temp
variable and 1 from mycounter
- With this approach I check every item with everyone and if a duplicate is found I return
True
otherwiseFalse
With this approach I have a huge time complexity, but it is a solution.
However, there is a solution which has only Big O of O(n)
which would be linear time complexity. Let's have a look on that one.
What is important is not to forget about the built-in methods which could help by solving the issue. In this particular use case we want to see duplicated items, so if the array would be sorted my next item would be the duplicate, if there is one.
- With the information above what we can do is we create again one variable called
length
and assign it the actual length of the array. - Now we do
nums.sort()
and with this one we have a sorted array. - In the next step we only need to loop through the array and in the if create a condition to check if my current item is equal to my next item and returning True or False
Basically again every problem can be solved in different ways. Just don’t forget to optimize your solution whenever possible but first make it work!