I haven't written here in a while (if you consider 4 months to be a while :)). You may ask why? Well, I have been busy. Busy becoming a better competitive programmer. It is a hassle but it is fun at the same time. So I thought why not write about that weekly? You know put my thought process of solving questions out here. This is a "killing two birds with one stone" kinda situation since I get to review my code and thought process while at the same time publish a blog for my readers.
Lists
In Python (the language I am currently using for solving LeetCode questions) arrays are known as lists. Lists are a consecutive array of data. In Python, lists are ordered starting from an index of 0. Their items are changeable and lists also allow for duplicate values. You can read more about lists here. Our Focus today will be on some LeetCode questions that revolve around manipulating and playing around with lists.
Questions
Whenever I start working on a new topic I usually like working with easier questions on that topic. Questions tagged as easy help me understand the basics of questions in that topic.
The idea is to validate if the given array has an element that appears more than once.
Initial Thoughts
class Solution(object):
def containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
dict_ = Counter(nums)
for value in dict_.values():
if value > 1:
return True
return False
Others' Solutions
In this section, I go through the "solutions" tab in LeetCode and look for other ways of solving the problem at hand. Doing this has helped me learn new tricks and new ways of solving problems that I hadn't initially thought about.
Solution 1
This one is pretty simple.
class Solution(object):
def containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
return len(nums) != len(set(nums))
It checks if the number of values in the list and the number of values in the set formed from that list are not equal. If they are equal it means there are no duplicates therefore it returns False else it returns True. This would be faster than my code since it iterates through the list only once. Also, the code is concise.
Time Complexity: O(n)
Solution 2
class Solution(object):
def containsDuplicate(self, nums):
hset = set()
for idx in nums:
if idx in hset:
return True
else:
hset.add(idx)
This is also straightforward. It uses a set to save the list's values in, then it uses that set to check if any of the values among the set's values repeat in the list. This is also faster than my code.
Time Complexity: O(n)
A follow-up to the previous question, this question is also tagged as easy. The idea is to return True when there are duplicates in the array that satisfy the condition that the absolute value of the difference of their indexes is less than or equal to a given value k.
Initial Thoughts
I first thought of using a set that saved tuples, where each tuple indicated the value of the number at a specific index and the index itself. But I quickly found out this would make finding the duplicate itself hard. For example, if I had a set: Set A = { (0,0),(0,1)} where SetA[0][0] would be the value of the num at index 0 on the list how would I be able to check if that exists in the set at O(1) time? Anyways this seemed too complicated for the task so I have another idea.
What if I used a dictionary to save the value of the index every time it finds a num in a list? Therefore anytime a number is in the dictionary it would calculate the absolute value of the difference between its index and the saved indices in the array. If it finds an index that satisfies this condition it returns True else it adds that index to the arr and continues iterating through the loop.
class Solution(object):
def containsNearbyDuplicate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
ndict = defaultdict(list)
for i in range(len(nums)):
if nums[i] in ndict:
v = ndict[nums[i]]
for idx in v:
if abs(idx - i) <= k:
return True
ndict[nums[i]].append(i)
else:
ndict[nums[i]].append(i)
return False
This is rather slow, however.
Time Complexity: O(n^2)
Other's Solutions
I found another solution that was much more concise and pretty similar to what I thought of.
Solution 1
def containsNearbyDuplicate(self, nums, k):
dic = {}
for i, v in enumerate(nums):
if v in dic and i - dic[v] <= k:
return True
dic[v] = i
return False
I was saving all the previous indices of every value until I found one that satisfied the condition however that was unnecessary. Let's say the list given was nums = [0,1,2,3,1,0,1] and k was 1. My code works here too since it saves every index but that isn't necessary since for example in this list the answer would be True because index 4 and index 6 satisfy the condition. Therefore saving the index of 1 at index 1 is useless because it won't satisfy the condition for any 1 that comes after the 1 that comes after it. So we could just save the values of the current num's index if the conditions aren't satisfied.
Here is a slight modification of my own to the code above.
class Solution(object):
def containsNearbyDuplicate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
ndict = defaultdict(int)
for i in range(len(nums)):
if nums[i] in ndict:
if abs(ndict[nums[i]]-i) <= k:
return True
ndict[nums[i]] = i
else:
ndict[nums[i]] = i
return False
Same idea here I just didn't use enumrate.
Time Complexity: O(n)
The idea is you are given a list of length - n. Your task is to find all the numbers in 1 - n that aren't included in the list you are given.
Initial Thoughts
So I thought, sort the list first and then iterate through it to append all the numbers that aren't equal to their respective index + 1. idx+1 != arr[idx]
class Solution(object):
def findDisappearedNumbers(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
nums.sort()
ans = []
for i, v in enumerate(nums,1):
if v != i:
ans.append(i)
return ans
Ok, so that didn't work. The problem with the approach is that sometimes the list may contain duplicate values. Let's say the list was lst = [1,2,2,3,3,4]. Although the ans list here should be [5,6] my code would return [2,3,4].
So I came up with another idea. How about I create a set of the given list and using a for loop iterate through the values from 1 - n and then append the values that aren't in the set to the list to be returned by the function?
class Solution(object):
def findDisappearedNumbers(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
nset = set(nums)
ans = []
for i in range(1,len(nums)+1):
if i not in nset:
ans.append(i)
return ans
This worked and it seems to be fast.
Time Complexity: O(n)
Done with the easy questions... I hope you found my review to your liking.
I will be diving into more challenging topics and providing insightful answers. Please stay tuned for upcoming posts, and I welcome any suggestions or requests for specific topics you would like me to address.
