This thread contains a list of leetcode questions which has been asked before in an interview. Before the interview day, I like to revise some problems that's why I have created this thread. Hope it is helpful for you too. Please let me know if you find new questions, I would be more than happy to add it to the list.
- Minimum Remove to Make Valid Parentheses
https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/
class Solution(object):
def minRemoveToMakeValid(self, s):
"""
:type s: str
:rtype: str
"""
stack =[]
s =list(s)
for i, char in enumerate(s):
if char == "(":
stack.append(i)
else:
if char == ")":
if stack:
stack.pop()
else:
s[i] = ""
while stack:
s[stack.pop()] = ""
return "".join(s)- Minimum Add to Make Parentheses Valid
https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/
class Solution(object):
def minAddToMakeValid(self, S):
"""
:type S: str
:rtype: int
"""
stack =[]
for i in S:
if i=="(":
stack.append(i)
else:
if i == ")":
if stack and stack[-1]=="(":
stack.pop()
else:
stack.append(i)
return len(stack)Check if a string is palindrome ignoring whitespace and special characters
https://stackoverflow.com/questions/25882015/check-if-a-string-is-palindrome-ignoring-whitespace-and-special-characters
def checkpalindrome(n):
n = n.lower()
n = ''.join(char for char in n if char.isalpha())
return n == n[::-1]- Valid Parentheses
https://leetcode.com/problems/valid-parentheses/
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
dic ={"{":"}",
"[":"]",
"(":")"}
stack = []
for i in s:
if i in dic:
stack.append(i)
# if there is input as "]", then we need to
# check the if the length of stack is empty or not.
elif len(stack) == 0 or dic[stack.pop()]!=i:
return False
return len(stack)==0- Longest Valid Parentheses
https://leetcode.com/problems/longest-valid-parentheses/
class Solution(object):
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
stack =[]
cur_long = 0
max_long = 0
for i in s:
if i == "(":
stack.append(cur_long)
cur_long =0
else:
if stack:
cur_long += stack.pop() + 2
max_long = max(cur_long, max_long)
else:
cur_long = 0
return max_long- Number of Islands
https://leetcode.com/problems/number-of-islands/
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j]== '1':
self.dfs(grid, i, j)
count +=1
return count
def dfs(self, grid, i, j):
if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j]!='1':
return
grid[i][j]= '#'
self.dfs(grid, i+1, j)
self.dfs(grid, i-1, j)
self.dfs(grid, i, j-1)
self.dfs(grid, i, j+1)
# BFS with Queue
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
count =0
directions = [(1,0), (-1, 0), (0, 1), (0, -1)]
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j]=="1":
q = deque([(i,j)])
grid[i][j] = '#'
while q:
r, c = q.popleft()
for x, y in directions:
nr = r +x
nc = c +y
if nr>=0 and nr< len(grid) and nc >=0 and nc <len(grid[0]) and grid[nr][nc]=='1':
q.append((nr, nc))
grid[nr][nc]= '#'
count +=1
return count
- Number of Closed Islands
https://leetcode.com/problems/number-of-closed-islands/
class Solution(object):
def closedIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
count = 0
for i in range(1, len(grid)-1):
for j in range(1, len(grid[0])-1):
if grid[i][j]==0 and self.dfs(grid, i, j):
count +=1
return count
def dfs(self, grid, i, j):
if grid[i][j]==1:
return True
if i<=0 or j<=0 or i>=len(grid)-1 or j>=len(grid[0])-1:
return False
grid[i][j]= 1
up=self.dfs(grid, i-1, j)
down=self.dfs(grid, i+1, j)
left=self.dfs(grid, i, j+1)
right=self.dfs(grid, i, j-1)
return up and down and left and rightclass Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dic = {}
for i in range(len(nums)):
if target-nums[i] in dic:
return [dic[target-nums[i]], i]
else:
dic[nums[i]] = i- Combination Sum II
https://leetcode.com/problems/combination-sum-ii/
class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
output = []
candidates.sort()
self.dfs(candidates, target, output, [])
return output
def dfs(self, candidates, target,output, path):
if target < 0:
return
if target == 0:
output.append(path)
for i in range(len(candidates)):
if i >0 and candidates[i]== candidates[i-1]:
continue
if candidates[i]> target:
break
self.dfs(candidates[i+1:], target - candidates[i], output , path + [candidates[i]])- Reverse Linked List
https://leetcode.com/problems/reverse-linked-list/
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev = None
while head:
cur = head
head = head.next
cur.next = prev
prev = cur
return prev- Reverse String
https://leetcode.com/problems/reverse-string/
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
left = 0
right = len(s)-1
while left < right:
temp = s[left]
s[left] = s[right]
s[right] = temp
left +=1
right -=1
return s- Reverse Words in a String
https://leetcode.com/problems/reverse-words-in-a-string/
class Solution:
def reverseWords(self, s: str):
s = s.split()
left = 0
right =len(s)-1
while left < right:
temp = s[left]
s[left]= s[right]
s[right] = temp
left +=1
right -=1
return " ".join(s[i] for i in range(len(s)))- Valid Anagram
https://leetcode.com/problems/valid-anagram/
class Solution(object):
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
dict = {}
for i in s:
if i not in dict:
dict[i]=1
else:
dict[i] +=1
for j in t:
if j not in dict:
return False
else:
dict[j] -=1
for k in dict:
if dict[k]!=0:
return False
return True- Valid Palindrome
https://leetcode.com/problems/valid-palindrome/
class Solution:
def isPalindrome(self, s: str) -> bool:
string1 = ""
for i in s:
if i.isalnum():
string1 += i.lower()
return string1 == string1[::-1]- Valid Palindrome II
https://leetcode.com/problems/valid-palindrome-ii/
class Solution:
def validPalindrome(self, s: str) -> bool:
def isPalin(s, l, r):
while l < r:
if s[l]!= s[r]:
return False
l +=1
r -=1
return True
left =0
right =len(s)-1
while left < right:
if s[left]!= s[right]:
return isPalin(s, left+1, right) or isPalin(s, left, right-1)
left +=1
right -=1
return TrueLRU Cache
https://leetcode.com/problems/lru-cache/
class Node():
def __init__(self, key, value):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache(object):
def __init__(self, capacity):
self.capacity = capacity
self.dic = dict()
self.head = Node(0,0)
self.tail = Node(0,0)
self.head.next = self.tail
self.tail.prev = self.head
def put(self, key, value):
if key in self.dic:
self.remove(self.dic[key])
node = Node(key,value)
self.add(node)
self.dic[key] = node
if len(self.dic) > self.capacity:
node = self.head.next
self.remove(node)
del self.dic[node.key]
def remove(self, node):
prev1 = node.prev
next1 = node.next
prev1.next = next1
next1.prev = prev1
def add(self, node):
prev1 = self.tail.prev
prev1.next = node
node.prev=prev1
node.next = self.tail
self.tail.prev = node
def get(self, key):
if key in self.dic:
node = self.dic[key]
self.remove(node)
self.add(node)
return node.value
return -1String compression
https://leetcode.com/problems/string-compression/
class Solution(object):
def compress(self, chars):
"""
:type chars: List[str]
:rtype: int
"""
i = 0
count =1
while i < len(chars)-1:
while i < len(chars)-1 and chars[i]== chars[i+1]:
count +=1
chars.pop(i+1)
if count >1:
for j in str(count):
chars.insert(i+1,j)
i +=1
count =1
i +=1
return len(chars)Merge Two Sorted Lists
https://leetcode.com/problems/merge-two-sorted-lists/
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
result = l3 = ListNode(0)
if not l1:
return l2
if not l2:
return l1
while l1 and l2:
if l1.val < l2.val:
l3.next = ListNode(l1.val)
l1 = l1.next
else:
l3.next = ListNode(l2.val)
l2 = l2.next
l3 = l3.next
if l1:
l3.next = l1
if l2:
l3.next = l2
return result.nextShuffle an Array
https://leetcode.com/problems/shuffle-an-array/
class Solution(object):
def __init__(self, nums):
"""
:type nums: List[int]
"""
self.nums = nums
def reset(self):
"""
Resets the array to its original configuration and return it.
:rtype: List[int]
"""
return self.nums
def shuffle(self):
"""
Returns a random shuffling of the array.
:rtype: List[int]
"""
return random.sample(self.nums, len(self.nums))- Shuffle the Array
https://leetcode.com/problems/shuffle-the-array/
class Solution(object):
def shuffle(self, nums, n):
"""
:type nums: List[int]
:type n: int
:rtype: List[int]
"""
output = []
n1 =nums[:n]
n2 = nums[n:]
i =0
while i < len(n1) and i <len(n2):
output.append(n1[i])
output.append(n2[i])
i +=1
return outputRotting Oranges
https://leetcode.com/problems/rotting-oranges/
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
level = 0
directions =[(-1, 0), (1, 0), (0, 1), (0, -1)]
q = deque([])
fresh = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j]==2:
q.append((i, j, level))
grid[i][j] = 0
if grid[i][j] == 1:
fresh +=1
while q:
r, c, level = q.popleft()
for x, y in directions:
nr = r + x
nc = c + y
if 0<=nr<len(grid) and 0<=nc<len(grid[0]) and grid[nr][nc]== 1:
q.append((nr,nc,level+1))
grid[nr][nc]=2
fresh -=1
if fresh > 0:
return -1
return levelFind All Duplicates in an Array
https://leetcode.com/problems/find-all-duplicates-in-an-array/
class Solution(object):
def findDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
nums.sort()
count = 0
output = []
if len(nums)==1:
return output
for i in range(1, len(nums)):
if nums[i] == nums[i-1]:
output.append(nums[i-1])
return output- Merge Sorted Array
https://leetcode.com/problems/merge-sorted-array/
class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: None Do not return anything, modify nums1 in-place instead.
"""
id1 = m-1
id2 = n-1
j = m + n - 1
while j >=0:
if id2>=0 and (m==0 or nums2[id2] >= nums1[id1]):
nums1[j] =nums2[id2]
id2 -=1
elif id2 > -1 and nums1[id1] > nums2[id2]:
nums1[j], nums1[id1] = nums1[id1], nums1[j]
if id1:
id1 -=1
j -=1
if id2 > -1:
for i in range(id2 +1):
nums1[i] =nums2[i]Merge k sorted Lists
https://leetcode.com/problems/merge-k-sorted-lists/
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
if not lists:
return
if len(lists) ==1:
return lists[0]
mid = len(lists)//2
l = self.mergeKLists(lists[:mid])
r = self.mergeKLists(lists[mid:])
return self.merge(l, r)
def merge(self, l, r):
result = l3 = ListNode(0)
while l and r:
if l.val < r.val:
l3.next = ListNode(l.val)
l = l.next
else:
l3.next = ListNode(r.val)
r = r.next
l3 = l3.next
l3.next = l or r
return result.nextProduct of Array Except Self
https://leetcode.com/problems/product-of-array-except-self/
class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
output = [1]*len(nums)
prod =1
for i in range(1,len(nums)):
prod *= nums[i-1]
output[i]*= prod
prod =1
for j in range(len(nums)-2, -1, -1):
prod *= nums[j+1]
output[j] *=prod
return outputImplement Trie
https://leetcode.com/problems/implement-trie-prefix-tree/submissions/
class Trie(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.root ={}
self.end = '*'
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: None
"""
node = self.root
for i in word:
if i not in node:
node[i]={}
node = node[i]
node[self.end] = True
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
node = self.root
for i in word:
if i not in node:
return False
node = node[i]
return self.end in node
def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
node = self.root
for i in prefix:
if i not in node:
return False
node = node[i]
return True
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)Longest common Prefix
https://leetcode.com/problems/longest-common-prefix/
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
output = ""
print(zip(*strs))
for i in zip(*strs):
if (i[0],) * len(i) == i:
output += i[0]
else:
break
return outputImplementing a Queue in Python
https://runestone.academy/runestone/books/published/pythonds/BasicDS/ImplementingaQueueinPython.html
class Queue:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0,item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
"""
q=Queue()
q.enqueue(4)
q.enqueue('dog')
q.enqueue(True)
print(q.size())
"""- Roman to Integer
https://leetcode.com/problems/roman-to-integer/
class Solution:
def romanToInt(self, s: str) -> int:
sum = 0
dic = { 'I' : 1,
'V' : 5,
'X' : 10,
'L' : 50,
'C' : 100,
'D' : 500,
'M' : 1000
}
for i in range(1, len(s)):
if dic[s[i-1]] < dic[s[i]]:
sum -= dic[s[i-1]]
else:
sum +=dic[s[i-1]]
print(i)
sum +=dic[s[-1]]
return sum- Convert Sorted Array to Binary Search Tree
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if not nums:
return
mid = len(nums)//2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid +1:])
return root- Check If a Word Occurs As a Prefix of Any Word in a Sentence
https://leetcode.com/problems/check-if-a-word-occurs-as-a-prefix-of-any-word-in-a-sentence/
class Solution(object):
def isPrefixOfWord(self, sentence, searchWord):
"""
:type sentence: str
:type searchWord: str
:rtype: int
"""
s = sentence.split(' ')
for i, w in enumerate(s):
if len(w) < len(searchWord):
continue
else:
if w[:len(searchWord)]== searchWord:
return i+1
return -1- Battleships in a Board
https://leetcode.com/problems/battleships-in-a-board/
# BFS with Queue
class Solution:
def countBattleships(self, board: List[List[str]]) -> int:
if not board:
return 0
output =0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j]=='X':
q = deque([(i, j)])
board[i][j]='#'
while q:
r, c = q.popleft()
for x, y in directions:
nr = r + x
nc = c + y
if nr>=0 and nr<len(board) and nc>=0 and nc<len(board[0]) and board[nr][nc]=='X':
q.append((nr, nc))
board[nr][nc] = '#'
output +=1
return output
# DFS recursively
class Solution:
def countBattleships(self, board: List[List[str]]) -> int:
output =0
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j]=='X':
self.dfs(board, i ,j)
output +=1
return output
def dfs(self, board, i, j):
if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or board[i][j]!='X':
return
board[i][j]='#'
self.dfs(board, i+1,j)
self.dfs(board, i-1, j)
self.dfs(board,i,j+1)
self.dfs(board, i, j-1)
# Using only O(1) extra memory and without modifying the value on board
class Solution:
def countBattleships(self, board: List[List[str]]) -> int:
if not board:
return 0
output =0
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j]=='.':
continue
if i > 0 and board[i-1][j] == 'X':
continue
if j > 0 and board[i][j-1] == 'X':
continue
output +=1
return output
- Reorder Data in Log Files
https://leetcode.com/problems/reorder-data-in-log-files/
class Solution:
def reorderLogFiles(self, logs: List[str]) -> List[str]:
letter_log = []
digit_log =[]
for i in range(len(logs)):
value = logs[i].split(' ')
if value[1].isdigit():
digit_log.append(logs[i])
elif value[1].isalnum():
letter_log.append(logs[i])
letter_log.sort(key=lambda x:x.split(' ')[0])
letter_log.sort(key=lambda x:x.split(' ')[1:])
letter_log.extend(digit_log)
return letter_log- Top K Frequent Words
https://leetcode.com/problems/top-k-frequent-words/
class Solution:
def topKFrequent(self, words: List[str], k: int) -> List[str]:
dic ={}
output =[]
for i in range(len(words)):
if words[i] not in dic:
dic[words[i]]=1
else:
dic[words[i]] +=1
sort_words = sorted(dic.items(), key=lambda x: (-x[1], x[0]))
for key, value in sort_words:
if len(output) < k:
output.append(key)
else:
break
return output
#Time complexity - O(N log N)
#Space complexity - O(N)- Maximum Depth of Binary Tree
https://leetcode.com/problems/maximum-depth-of-binary-tree/
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
left1 = self.maxDepth(root.left)
right1 = self.maxDepth(root.right)
return max(left1, right1) +1- Maximum Depth of N-ary Tree
https://leetcode.com/problems/maximum-depth-of-n-ary-tree/
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def maxDepth(self, root: 'Node') -> int:
if not root:
return 0
if not root.children:
return 1
depth =[]
for child in root.children:
depth.append(self.maxDepth(child))
return max(depth) +1- K Closest Points to Origin
https://leetcode.com/problems/k-closest-points-to-origin/
import heapq
class Solution:
def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
heap = []
for (x, y) in points:
dist= -(x*x + y*y)
if len(heap) == K:
heapq.heappushpop(heap, (dist, x, y))
else:
heapq.heappush(heap, (dist, x, y))
output = []
for (dist, x, y) in heap:
output.append((x, y))
return output
#inserting an item in the heap is logk
#Time complexity - O(N logk)
#Space - O(K)Write a program to return the values that leads to null.
""""
Input:
{
"Jon": "Smith",
"Adam": ["Jake", null, "Nancy"],
"Alex": {
"Muller": [null, "Sam"],
"Phil": null,
"Xav": ["Mike", "Tom"]
}
"Lex": null,
}
Output: ["Adam.1", "Alex.Muller.0", "Alex.Phil", "Lex"]
""""
import json
def path_to_null(json_str):
json_dict = json.loads(json_str)
path, res = [], []
find_null(json_dict, path, res)
return res
def find_null(node, path, res):
if node is None:
res.append(".".join(path))
return
if isinstance(node, list):
for idx, item in enumerate(node):
path.append(str(idx))
find_null(item, path, res)
path.pop()
if isinstance(node, dict):
for k, v in node.items():
path.append(k)
find_null(v, path, res)
path.pop()
json_str = '{"Jon": "Smith", "Adam": ["Jake", null, "Nancy"], "Alex": { "Muller": [null, "Sam"],\
"Phil": null, "Xav": ["Mike", "Tom"] }, "Lex": null}'
print(path_to_null(json_str))- Group Anagrams
https://leetcode.com/problems/group-anagrams/
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
dic= {}
for w in strs:
key = tuple(sorted(w))
dic[key] = dic.get(key, []) + [w]
return dic.values()
# return sorted(dic.values())- Find Median from Data Stream
https://leetcode.com/problems/find-median-from-data-stream/
import heapq
class MedianFinder:
def __init__(self):
"""
initialize your data structure here.
"""
self.small = []
self.large = []
def addNum(self, num: int) -> None:
if len(self.small) == len(self.large):
heappush(self.large, -heappushpop(self.small, -num))
else:
heappush(self.small, -heappushpop(self.large, num))
def findMedian(self) -> float:
if len(self.small) == len(self.large):
return float(self.large[0] - self.small[0])/ 2.0
else:
return float(self.large[0])
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()- HTML Entity Parser
https://leetcode.com/problems/html-entity-parser/
class Solution:
def entityParser(self, text: str) -> str:
dic = {""": '"',
"'" : "'",
">": ">",
"<": "<",
"⁄" : "/",
"&": "&"}
for k, v in dic.items():
text =text.replace(k, v)
return text
- Insert Delete GetRandom O(1)
https://leetcode.com/problems/insert-delete-getrandom-o1/
import random
class RandomizedSet(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.dic = {}
self.value = []
def insert(self, val):
"""
Inserts a value to the set. Returns true if the set did not already contain the specified element.
:type val: int
:rtype: bool
"""
if val in self.dic:
return False
self.dic[val] = len(self.value)
self.value.append(val)
return True
def remove(self, val):
"""
Removes a value from the set. Returns true if the set contained the specified element.
:type val: int
:rtype: bool
"""
if val not in self.dic:
return False
last_elem = self.value[-1]
val_remove = self.dic[val]
self.dic[last_elem] = val_remove
self.value[val_remove] = last_elem
self.value[-1] =val
self.value.pop()
self.dic.pop(val)
return True
def getRandom(self):
"""
Get a random element from the set.
:rtype: int
"""
return random.choice(self.value)
# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()- Design HashMap
https://leetcode.com/problems/design-hashmap/
class Node():
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None
class MyHashMap(object):
def __init__(self):
self.capacity = 1000
self.hash_table = [None]* self.capacity
def hash(self, key):
index = key % self.capacity
return index
def put(self, key, value):
index = self.hash(key)
if self.hash_table[index] == None:
self.hash_table[index] = Node(key, value)
else:
curr_node = self.hash_table[index]
while curr_node:
if curr_node.key == key:
curr_node.value = value
return
if curr_node.next == None:
break
curr_node = curr_node.next
curr_node.next = Node(key, value)
def get(self, key):
index = self.hash(key)
curr_node =self.hash_table[index]
while curr_node:
if curr_node.key == key:
return curr_node.value
else:
curr_node= curr_node.next
return -1
def remove(self, key):
index = self.hash(key)
if self.hash_table[index]== None:
return
curr_node = prev_node = self.hash_table[index]
if curr_node.key == key:
self.hash_table[index] = curr_node.next
else:
curr_node = curr_node.next
while curr_node:
if curr_node.key == key:
prev_node.next = curr_node.next
break
else:
prev_node = prev_node.next
curr_node = curr_node.next
# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)- Defanging an IP Address
https://leetcode.com/problems/defanging-an-ip-address/
class Solution(object):
def defangIPaddr(self, address):
"""
:type address: str
:rtype: str
"""
# x = address.replace(".", "[.]")
# return x
# OR
result = ''
ch = '[.]'
for i in address:
if i == '.':
i = ch
result +=i
return result- Kids With the Greatest Number of Candies
https://leetcode.com/problems/kids-with-the-greatest-number-of-candies/
class Solution(object):
def kidsWithCandies(self, candies, extraCandies):
"""
:type candies: List[int]
:type extraCandies: int
:rtype: List[bool]
"""
max_candies = max(candies)
print(max_candies)
output =[]
for i in candies:
if i+extraCandies >=max_candies:
output.append(True)
else:
output.append(False)
return output- Number of Good Pairs
https://leetcode.com/problems/number-of-good-pairs/
Solution1: Brute force
TC= O(n*2)
SC O(n)
class Solution(object):
def numIdenticalPairs(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
count =0
for i in range(len(nums)):
for j in range(len(nums)):
if nums[i]==nums[j] and i<j:
count +=1
return countSolution2 : Optimize in O(n)
TC O(n)
SC O(n)
class Solution(object):
def numIdenticalPairs(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dic = {}
count =0
for num in nums:
if num in dic:
count +=dic[num]
dic[num] +=1
else:
dic[num] =1
return count- Jewels and Stones
https://leetcode.com/problems/jewels-and-stones/
class Solution(object):
def numJewelsInStones(self, J, S):
"""
:type J: str
:type S: str
:rtype: int
"""
count = 0
for i in S:
if i in J:
count +=1
return count- Maximum Nesting Depth of the Parentheses
https://leetcode.com/problems/maximum-nesting-depth-of-the-parentheses/
class Solution(object):
def maxDepth(self, s):
"""
:type s: str
:rtype: int
"""
depth = max_count = 0
for i in s:
if i == "(":
depth +=1
elif i == ")":
if depth > max_count:
max_count = depth
depth -=1
else:
continue
return max_count- Shuffle String
https://leetcode.com/problems/shuffle-string/
class Solution(object):
def restoreString(self, s, indices):
"""
:type s: str
:type indices: List[int]
:rtype: str
"""
output = ['']*len(s)
for i in range(len(s)):
output[indices[i]] = s[i]
return ''.join(j for j in output)- Number of Steps to Reduce a Number to Zero
https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/submissions/
class Solution(object):
def numberOfSteps (self, num):
"""
:type num: int
:rtype: int
"""
count =0
while num:
if num%2 ==0:
num /= 2
else:
num -=1
count +=1
return count- Matrix Diagonal Sum
https://leetcode.com/problems/matrix-diagonal-sum/
class Solution(object):
def diagonalSum(self, mat):
"""
:type mat: List[List[int]]
:rtype: int
"""
mid = len(mat)//2
sum1 = 0
for i in range(len(mat)):
sum1 += mat[i][i]
sum1 +=mat[len(mat)-1-i][i]
if len(mat)%2==1:
sum1 -=mat[mid][mid]
return sum1Comments (4)