arrays and hashing

Question 1

contains duplicate
https://leetcode.com/problems/contains-duplicate/description/

Answer 1

make hashset
iterate through input array
if number is in the hashset return true
otherwise add number to hashset

Question 2

two sum
https://leetcode.com/problems/two-sum/

Answer 2

prevmap = {}

    for i, n in enumerate(nums):
        dif = target - n
        if  dif in prevmap:
            return [prevmap[dif], i]
        prevmap[n] = i
    return None

Question 3

valid anagram
https://leetcode.com/problems/valid-anagram/

Answer 3

if len(s) != len(t):
return False

    countS, countT = {}, {}

    for i in range(len(s)):
        countS[s[i]] = 1 + countS.get(s[i], 0)
        countT[t[i]] = 1 + countT.get(t[i], 0)

    return countS == countT

Question 4

is subsequence
https://leetcode.com/problems/is-subsequence/description/

Answer 4

i, j = 0, 0

    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
        j += 1
    if i == len(s):
        return True
    else:
        return False

Question 5

length of last word
https://leetcode.com/problems/length-of-last-word/

Answer 5

i, length = len(s) - 1, 0

    while s[i] == " ":
        i -= 1
    while i >= 0 and s[i] != " ":
        length += 1
        i -= 1
    return length

Question 6

longest common prefix
https://leetcode.com/problems/longest-common-prefix/submissions/

Answer 6

res = “”
for i in range(len(strs[0])):
for s in strs:
if i == len(s) or s[i] != strs[0][i]:
return res
res += strs[0][i]
return res

Question 7

pascal’s triangle
https://leetcode.com/problems/pascals-triangle/submissions/

Answer 7

def generate(self, rowIndex) -> List[List[int]]:
if rowIndex == 0:
return [[1]]
else:
return self.getAllRow(rowIndex - 1)

def getAllRow(self, rowIndex):
    if rowIndex == 0:
        return [[1]]
    ListPrec = self.getAllRow(rowIndex - 1)
    Len = len(ListPrec[-1])
    ListPrec.append([1])
    for i in range(0, Len - 1):
        ListPrec[-1].append(ListPrec[-2][i] + ListPrec[-2][i + 1])
    ListPrec[-1].append(1)
    return ListPrec

Question 8

remove element
https://leetcode.com/problems/remove-element/description/

Answer 8

k = 0

    for i in range(len(nums)):
        if nums[i] != val:
            nums[k] = nums[i]
            k += 1
    
    return k

Question 9

unique email address
https://leetcode.com/problems/unique-email-addresses/description/

Answer 9

unique_emails: set[str] = set()
for email in emails:
local_name, domain_name = email.split(‘@’)
local_name = local_name.split(‘+’)[0]
local_name = local_name.replace(‘.’, ‘’)
email = local_name + ‘@’ + domain_name
unique_emails.add(email)
return len(unique_emails)

Question 10

isomorphic strings
https://leetcode.com/problems/isomorphic-strings/description/

Answer 10

mapST, mapTS = {}, {}

    for c1, c2 in zip(s, t):
        if (c1 in mapST and mapST[c1] != c2) or (c2 in mapTS and mapTS[c2] != c1):
            return False
        mapST[c1] = c2
        mapTS[c2] = c1

    return True

Question 11

remove duplicate from sorted array
https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/

Answer 11

l = 1

    for r in range(1, len(nums)):
        if nums[r] != nums[r - 1]:
            nums[l] = nums[r]
            l += 1

    return l

Question 12

concatenation of array
https://leetcode.com/problems/concatenation-of-array/description/

Answer 12

ans = []

    for i in range(2):
        for n in nums:
            ans.append(n)

    return ans

Question 13

minimum stack
https://neetcode.io/problems/minimum-stack

Answer 13

def __init__(self):
self.stack = []
self.minStack = []

def push(self, val: int) -> None:
    self.stack.append(val)
    val = min(val, self.minStack[-1] if self.minStack else val)
    self.minStack.append(val)

def pop(self) -> None:
    self.stack.pop()
    self.minStack.pop()

def top(self) -> int:
    return self.stack[-1]

def getMin(self) -> int:
    return self.minStack[-1]

Question 14

valid parentheses
https://leetcode.com/problems/valid-parentheses/description/

Answer 14

stack = []
closeToOpen = {“)” : “(“, “]” : “[”, “}” : “{“}

    for c in s: 
        if c in closeToOpen:
            if stack and stack[-1] == closeToOpen[c]:
                stack.pop()
            else:
                return False
        else:
            stack.append(c)
    
    return True if not stack else False