Problem 1: Contains Duplicate
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.
Solution 1: time=O(n) and space=O(n)
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
output = []
for i in nums:
if i not in output:
output.append(i)
if output == nums:
return False
else:
return True
Solution 2: time=O(n) and space=O(n)
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
data = set()
for i in nums:
if i in data:
return True
data.add(i)
return False Problem 2: Valid Anagram
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Solution 1: time=O(n) and space=O(n)
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
s_counter, t_counter = {}, {}
for i in s:
s_counter[i] = 1 + s_counter.get(i,0)
for j in t:
t_counter[j] = 1 + t_counter.get(j,0)
if s_counter == t_counter:
return True
else:
return False
Solution 2: time=O(n) and space=O(n)
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
ch_data = [0]*26
for i in s:
ch_data[ord(i)-ord("a")] += 1
for j in t:
ch_data[ord(j)-ord("a")] -= 1
for ch in ch_data:
if ch != 0:
return False
return TrueProblem 3: Concatenation of Array
Given an integer array nums of length n, you want to create an array ans of length 2n where ans[i] == nums[i] and ans[i + n] == nums[i] for 0 <= i < n (0-indexed).
Specifically, ans is the concatenation of two nums arrays.
Return the array ans.
Solution 1: Time=O(n), Space=O(n).
class Solution:
def getConcatenation(self, nums: List[int]) -> List[int]:
ans = [0]*2*len(nums)
for index, value in enumerate(nums):
ans[index] = value
ans[index+len(nums)] = value
return ans
Solution 2:
class Solution:
def getConcatenation(self, nums: List[int]) -> List[int]:
ans = []
for i in nums:
ans.append(i)
for i in nums:
ans.append(i)
return ans
Problem 4: Replace Elements with Greatest Element on Right Side
Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1.
After doing so, return the array.
Solution 1: brute force. Time=O(n^2)
Solution 2: look for the max from the right. time=O(n)
class Solution:
def replaceElements(self, arr: List[int]) -> List[int]:
ans,current_max = [], -1
if len(arr) == 1:
return [-1]
for i in arr[::-1]:
ans.insert(0,current_max)
if i > current_max:
current_max = i
return ans
Problem 5: Is Subsequence
Given two strings s and t, return true if s is a subsequence of t, or false otherwise.
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., “ace” is a subsequence of “abcde” while “aec” is not).
Solution: Go through each of the elements in t to make sure we have the ch per s. only go through t once. time = O(n)
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
if len(s) == 0:
return True
i, j = 0,0
while j < len(t) and i < len(s):
if s[i] != t[j]:
j = j + 1
else:
i = i + 1
j = j + 1
return False if j == len(t) and i < len(s) else TrueProblem 6: Length of Last Word
solution1: use brute force using strip and split string methods
solution 2: start the last of the string and look for len of 1st word:
len_last_str = 0
for i in s[::-1]:
if ord("a") <= ord(i.lower()) <= ord("z"):
len_last_str += 1
elif len_last_str > 0 and i == " ":
break
return len_last_strProblem 7 : Two Sum
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums_dict = {}
for index, value in enumerate(nums):
if target-value not in nums_dict.keys():
nums_dict[value] = index
else:
return [nums_dict[target-value], indexProblem 8 :Longest Common Prefix
Unable to solve
Problem 9 : 49. Group Anagrams
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
output = defaultdict(list)
for word in strs:
temp_list = [0]*26
for ch in word:
temp_list[ord(ch)-ord("a")] += 1
output[tuple(temp_list)].append(word)
return [v for v in output.values()]
Problem 9: Fizz Buzz
class Solution:
def fizzBuzz(self, n: int) -> List[str]:
answer = []
for i in range(1,n+1):
if i%3==0 and i%5==0:
answer.append("FizzBuzz")
elif i%3==0:
answer.append("Fizz")
elif i%5==0:
answer.append("Buzz")
else:
answer.append(str(i))
return answerProblem 10: Remove Element
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
k, positive_inf = 0, float("inf")
for index, value in enumerate(nums):
if nums[index] == val:
k +=1
nums[index] = positive_inf
nums.sort()
return len(nums) - k
Problem 11: Unique Email Addresses
class Solution:
def numUniqueEmails(self, emails: List[str]) -> int:
unique_emails = set()
for email in emails:
local_name, domain = email.split("@", maxsplit=1)
if "." in local_name:
local_name = "".join(local_name.split("."))
if "+" in local_name:
local_name = (local_name.split("+"))[0]
true_email = local_name + "@" + domain
unique_emails.add(true_email)
return len(unique_emails) Problem 12: Can Place Flowers
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
if n == 0:
return True
new_fb = [0] + flowerbed + [0]
for i in range(1, len(new_fb)-1):
if new_fb[i] == 0 and new_fb[i+1] == 0 and new_fb[i-1] == 0:
new_fb[i] = 1
n = n-1
if n == 0:
return True
return FalseProblem 13: Majority Element
solution1: time = O(n), space = O(n)
class Solution:
def majorityElement(self, nums: List[int]) -> int:
temp_dict , initial_count, output = {}, 0, 0
for i in nums:
temp_dict[i] = 1 + temp_dict.get(i,0)
for key, value in temp_dict.items():
if value > initial_count:
initial_count = value
output = key
return output
solution 2: time=O(n), space = O(1)
class Solution:
def majorityElement(self, nums: List[int]) -> int:
element, count = 0,0
for i in nums:
if count == 0:
element = i
if i == element:
count += 1
else:
count -= 1
return elementProblem 14: Next Greater Element I