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
def knapsackUtil(wt, val, n, W):
# weights[], values[], items, capacity
dp = [[-1] * (W + 1) for _ in range(n + 1)]
# base conditions
for i in range(W + 1):
dp[0][i] = 0
for i in range(n + 1):
dp[i][0] = 0
# recursive case
for i in range(1, n + 1):
for j in range(1, W + 1):
if wt[i - 1] <= j:
dp[i][j] = max(dp[i - 1][j - wt[i - 1]] + val[i - 1], dp[i - 1][j])
else:
dp[i][j] = dp[i - 1][j]
return dp[n][W]
def subsetSumUtil(wt, n):
n, s = len(wt), sum(wt)
if s % 2 != 0:
return 0
s //= 2 # target sum
dp = [[-1] * (s + 1) for _ in range(n + 1)]
for j in range(s + 1):
dp[0][j] = 0
for i in range(n + 1):
dp[i][0] = 1
for i in range(1, n + 1):
for j in range(1, s + 1):
if wt[i - 1] <= j:
dp[i][j] = (dp[i - 1][j - wt[i - 1]] + dp[i - 1][j])
else:
dp[i][j] = dp[i - 1][j]
return dp[n][s]
Manachar’s Algorithm
def longestPalindrome(self, s): # manachar's algorithm
# Transform S into T.
# For example, S = "abba", T = "^#a#b#b#a#$".
# ^ and $ signs are sentinels appended to each end to avoid bounds checking
T = '#'.join('^{}$'.format(s))
n = len(T)
P = [0] * n
C = R = 0
for i in range (1, n-1):
P[i] = (R > i) and min(R - i, P[2*C - i]) # equals to i' = C - (i-C)
# Attempt to expand palindrome centered at i
while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
P[i] += 1
# If palindrome centered at i expand past R,
# adjust center based on expanded palindrome.
if i + P[i] > R:
C, R = i, i + P[i]
# Find the maximum element in P.
maxLen, centerIndex = max((n, i) for i, n in enumerate(P))
return s[(centerIndex - maxLen)//2: (centerIndex + maxLen)//2]
KMP String Matching Algorithm
def calcLPS(pattern) -> list[int]: # LPS - longest prefix suffix array
m = len(pattern) # length of the pattern string
lps = [0] * (m + 1)
lps[0] = -1 # dummy value
j = 0 # initial prefix length
i = 1
while i < m: # O(m)
if pattern[j] == pattern[i]:
i += 1
j += 1
lps[i] = j
elif j > 0:
j = lps[j]
else:
i += 1
lps[i] = 0
return lps
def KMPsearch(text, pattern) -> list[str]:
pos_t = 0
pos_p = 0
n = len(text)
m = len(pattern)
matches = []
prefix = calcLPS(pattern)
while pos_t < n:
if pattern[pos_p] == text[pos_t]:
pos_p += 1
pos_t += 1
if pos_p == m:
matches.append(pos_t - pos_p)
pos_p = prefix[pos_p]
else:
pos_p = prefix[pos_p]
if pos_p < 0:
pos_t += 1
pos_p += 1
return matches