Kadane’s Algorithm
class Solution:
def maxSubArray(self, arr):
max_value=arr[0]
min_value=arr[0]
ans=arr[0]
for i in range(1,len(arr)): #using DP approach
choice1=arr[i]*max_value # + for subarraysum, * for subarrayproduct
choice2=arr[i]*min_value # + for subarraysum, * for subarrayproduct
# if -ve ele then min +/* ele, else max +/* ele, also compare ele alone by itself
max_value=max(arr[i],choice1,choice2) # local maximum
min_value=min(arr[i],choice1,choice2) # local minimum
ans=max(ans,max_value) # global maximum
return(ans)
Depth First Search on 2D Arrays (Grid DFS, Flood Fill)
class Solution:
def uniquePathsIII(self, grid):
self.ans = 0
m = len(grid)
n = len(grid[0])
notvisited = 1
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
x, y = i, j # starting square found
elif grid[i][j] == 0:
notvisited += 1 # empty square found
def isvalid(x, y):
return (0 <= x < m and 0 <= y < n and grid[x][y] >= 0)
def dfs(x, y, notvisited):
if not isvalid(x, y):
return
if grid[x][y] == 2: # if ending square
if notvisited == 0:
self.ans += 1
return
grid[x][y] = -2 # mark visited
dfs(x - 1, y, notvisited - 1) # left
dfs(x + 1, y, notvisited - 1) # right
dfs(x, y - 1, notvisited - 1) # up
dfs(x, y + 1, notvisited - 1) # down
grid[x][y] = 0 # unmark visited
dfs(x, y, notvisited)
return self.ans
class Solution:
def countSubIslands(self, grid1, grid2):
m, n = len(grid1), len(grid1[0])
def check(x, y):
if x < 0 or x >= m:
return 0
if y < 0 or y >= n:
return 0
if grid2[x][y] == 0:
return 0
return 1
def fill(x, y):
if check(x, y) == 0:
return 1
if grid2[x][y] == 1 and grid1[x][y] == 0:
return 0
grid2[x][y] = 0
res = fill(x + 1, y) & fill(x - 1, y) & fill(x, y + 1) & fill(x, y - 1)
return res
ans = 0
for i in range(m):
for j in range(n):
if grid1[i][j] == 1 and grid2[i][j] == 1:
ans += fill(i, j) > 0
return ans
Binary Search
def binarySearch(arr, key): # search lower bound(key)
beg, end = 0, len(arr) - 1
found = False
ind = -1
while beg <= end:
mid = beg + (end - beg) // 2 # to avoid mid overflow
if key == arr[mid]: # condition
found = True
ind = mid
# end = mid - 1 # lower bound
break # traditional BS
elif key < arr[mid]:
end = mid - 1
else:
beg = mid + 1
if not found: # insertion point = beg (beg < end == True)
return -1
else:
return ind
Binary Exponentiation
def findpow_iter(a, b, m = int(1e9 + 7)): #iterative
if a == 0:
return 0
res = 1
while b > 0:
if b & 1:
res = res * a % m
a = a * a % m
b >>= 1
return res % m
Binary Tree
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def preorder(self, root): # root - Node type
nodes = []
def TraversalUtil(root):
if not root:
return
nodes.append(root.val)
for child in root.children:
TraversalUtil(child)
# if root.left:
# TraversalUtil(root.left)
# if root.right:
# TraversalUtil(root.right)
TraversalUtil(root)
return nodes
"""
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 levelOrder(self, root):
queue = []
if root: queue.append(root)
levels = []
while queue:
sz = len(queue)
level = []
for i in range(sz):
x = queue.pop(0)
level.append(x.val)
if x.left: queue.append(x.left)
if x.right: queue.append(x.right)
levels.append(level)
return levels if root else []
Prefix Sum (Subarray)
import collections
class Solution:
def subarraySum(self, nums, k):
n= len(nums)
hp = collections.defaultdict(lambda:0)
ans = 0
presum = [0,] # prefix sum = cummulative sum
for i in range(1, n + 1):
presum.append(presum[-1] + nums[i - 1])
if presum[i] == k:
ans += 1
if hp[presum[i] - k] > 0:
ans += hp[presum[i] - k]
hp[presum[i]] += 1
return ans
class Solution:
def checkSubarraySum(self, nums, k):
dic = {0:-1} # storing indices
summ = 0
for i, n in enumerate(nums):
summ = (summ + n) % k
if summ not in dic:
dic[summ] = i
else:
if i - dic[summ] >= 2:
return True
return False
Monotonic Stack & Queue
class Solution:
def monotonicstack(self, arr, n):
''' Returns the index of NGE '''
stack = [] # monotonic stack
nge = [0] * n
for i in range(n - 1, -1, -1):
while stack != [] and arr[i % n] >= arr[stack[-1]]:
stack.pop()
if stack == []:
nge[i % n] = -1
else:
nge[i % n] = stack[-1]
stack.append(i % n)
return nge # next greater element array
# greater = self.monotonicstack(arr, n)
class Solution:
def maxSlidingWindow(self, arr, k):
queue = [] # monotonic double ended queue
ans = []
for i in range(len(arr)):
while queue != [] and arr[queue[-1]] < arr[i]:
queue.pop()
queue.append(i)
while queue[0] <= i - k: # if windows overflow, keep popping from beginning
queue.pop(0)
if i >= k - 1: # when window is full, keep finding the max element
ans.append(arr[queue[0]])
return ans
class Solution:
def largestRectangleArea(self, heights):
maxarea = 0
pstack, hstack = [], []
currarea, maxarea = 0, 0
heights.append(0)
for i in range(len(heights)): # O(n)
prevwidth = int(1e9)
while hstack != [] and hstack[-1] > heights[i]: # condition 1
prevwidth = pstack[-1]
width = i - pstack.pop()
height = hstack.pop()
currarea = width * height
maxarea = max(currarea, maxarea)
if hstack == [] or hstack[-1] < heights[i]: # condition 2
hstack.append(heights[i])
pstack.append(min(prevwidth, i))
return maxarea
Sieve of Eratosthenes (Prime Numbers)
def get_primes(n):
is_prime = [1] * (n + 1) # [0.....N]
is_prime[0], is_prime[1] = 0, 0 # make 0 and 1 NOT PRIME
for i in range(4, n + 1, 2): # make even nos. NOT PRIME
is_prime[i] = 0
for i in range(3, int(n ** 0.5 + 2), 2):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = 0
return is_prime
Prefix - Suffix GCD
def gcd_iter(a, b):
while(b):
a, b = b, a % b
return a
# print(gcd_iter(13, 19))
def gcd_recur(a, b):
if b == 0:
return a
return gcd(b, a % b)
# print(gcd_recur(13, 19))
import math, collections
for tc in range(int(input())):
n = int(input())
arr = list(map(int, input().split()))
x = arr[0]
for i in range(1, n):
x = math.gcd(x, arr[i])
if x != 1:
print(n)
continue
else:
def maxGCD(arr, n):
prefix = [0] * n
suffix = [0] * n
prefix[0] = arr[0]
suffix[n - 1] = arr[n - 1]
for i in range(1, n):
prefix[i] = math.gcd(prefix[i - 1], arr[i])
for i in range(n - 2, -1, -1):
suffix[i] = math.gcd(suffix[i + 1], arr[i])
hp = collections.defaultdict(lambda:0)
for i in range(1, n - 1):
y = math.gcd(prefix[i - 1], suffix[i + 1])
if y != 1:
hp[y] += 1
if suffix[1] != 1:
hp[suffix[1]] += 1
if prefix[n - 2] != 1:
hp[prefix[n - 2]] += 1
return len(hp)
y = maxGCD(arr, n)
print(y)
Dynamic Programming - Type 1 - Knapsack
Manachar’s Algorithm
KMP String Matching Algorithm