algorithms: contains the solutions to the problems of the algorithmic toolbox course
data structures: contains the solutions to the problems of the data structures course
graphs: contains the solutions to the problems of the algorithm on graphs course
all the implementation are in python only. it contains the solutions of most of the problems, not all❕
Issue: Optimal way of searching using DFS(Depth First Search algorithm). Problem link
Hint: Refer this video for understanding DFS.
Approach: Depth-first search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. So the basic idea is to start from the root or any arbitrary node and mark the node and move to the adjacent unmarked node and continue this loop until there is no unmarked adjacent node. Then backtrack and check for other unmarked nodes and traverse them.
Implementation
classSolution:
deflongestIncreasingPath(self, matrix: List[List[int]]) ->int:
ifnotmatrix:
return0rows=len(matrix)
cols=len(matrix[0])
traced= {}
ans=0foriinrange(rows):
forjinrange(cols):
path=self.search(matrix, i, j, traced) ans=max(ans, path)
returnansdefsearch(self, matrix, i, j, traced):
rows=len(matrix)
cols=len(matrix[0])
if (i,j) intraced:
returntraced.get((i,j))
dirs= [(-1,0),(1,0),(0,1),(0,-1)] path=1forx, yindirs:
new_x=x+inew_y=y+jifrows>new_x>=0andcols>new_y>=0andmatrix[new_x][new_y]>matrix[i][j]:
path=max(path, 1+self.search(matrix, new_x, new_y, traced))
traced[(i,j)] =pathreturntraced[(i,j)]Issue: this current implementation is using runtine complexity as O(N^4), try to optimize it. Problem link
Hint: For each 0, change it to a 1, then do a depth first search to find the size of that component. The answer is the maximum size component found.
Implementation
classSolution:
deflargestIsland(self, grid: List[List[int]]) ->int:
defsearch(i,j):
seen= {(i,j)}
stack= [(i,j)]
whilestack:
i,j=stack.pop()
fornew_i,new_jin ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
if0<=new_i<len(grid) and0<=new_j<len(grid[0]) and (new_i,new_j) notinseenandgrid[new_i][new_j]:
stack.append((new_i, new_j))
seen.add((new_i, new_j))
returnlen(seen)
has_zero=Falseans=0foriinrange(0, len(grid)):
forjinrange(0, len(grid[0])):
ifgrid[i][j]==0:
has_zero=Truegrid[i][j]=1ans=max(ans, search(i,j))
grid[i][j]=0returnansifhas_zeroelselen(grid)*len(grid[0])Issue: dynamic programming problem link
Hint: revert back from the final position
Basically, this problem would work from front to back, but the optimal solution for traversing from (0, 0) to (i, j) will not always give us the optimal solution for (i + 1, j) and (i, j + 1). Sometimes it is better to take the locally worse route to be able to have enough HP so that the negatives that will be encountered later are minimized.
However, if we work in reverse, we can avoid this. Start from (n - 1, m - 1), where n is the number of rows, and m is the number of columns. In order to make the space complexity O(N), we use the concept of time iterations.
at t=0, the Knight is at (0, 0)
at t=1, the Knight is at (1,0) or (0,1)
at t=2, the Knight is at (2,0), (1,1) or (0,2)
So, we can sort of make the relation between t and an arbitrary point (i, j) that the knight may be: t = i + j. Therefore, we can iterate through all of the t values, and store them in a dp array of size n.
Note that this dp only stores values of the rows. that's because if we know the row and the current time, then we know the column j = t - i.
So, we can see that there are n + m - 1 iterations of t: [0, n + m - 2], and in order to start out the dp, we go ahead and calculate dp[n-1], which corresponds to t = n + m - 2, and dungeon[n - 1][m - 1]
Here's an example runthrough of the logic:
[[-2,-3,3],
[-5,-10,1],
[10,30,-5]]
Initialize dp with dungeon[n - 1][m - 1]
t = 4 i = 2, j = 2, the -5 means we need 1 - (-5) HP = 6HP.... dp = [inf, inf, 6]
t = 3 i = 2, j = 1 the 30 > 6, so we dont need 6 minHP anymore, minHP = 1
t = 3 i = 1, j = 3 the 1 < 6, so we need 1 less HP, so minHP = 6 - 1 = 5
...dp = [inf, 5, 1]
t = 2 i = 2 j = 0. the 10 > 1, so we still need 1
t = 2 i = 1 j = 1. the -10 < 1 and -10 < 5 minHP = min(1, 5) - (-10) = 11
t = 2 i = 0 j = 2. the 3 < 5 so minHP = 5 - 3 = 2
...dp = [2,11,1]
t = 1 i = 1 j = 0 the -5 < 11, and -5 < 1 so minHP = min(1, 11) - (-5) = 6
t = 1 i = 0 j = 1 the -3 < 2 and -3 < 11 so minHP = min(2, 11) - (-3) = 5
...dp = [5, 6, inf]
t = 0 i = 0 j = 0. the -2 < 5 and -2 < 6 so minHP = min(5, 6) -(-2) = 7HP
...dp = [7,inf,inf]
then return dp[0] = 7
Implementation
classSolution:
defcalculateMinimumHP(self, dungeon: List[List[int]]) ->int:
n=len(dungeon)
m=len(dungeon[0])
dp= [float('inf') for_inrange(len(dungeon))]
ifdungeon[n-1][m-1] >=0:
dp [n-1] =1else:
dp[n-1] =1-dungeon[n-1][m-1]
fortinrange(n+m-3, -1, -1):
dp2= [float('inf') for_inrange(n)]
foriinrange(max(0, t-m+1), min(n, t+1)):
j=t-iifi+1<n:
ifdungeon[i][j] <dp[i+1]:
dp2[i] =dp[i+1] -dungeon[i][j]
else:
dp2[i] =1ifj+1<m:
ifdungeon[i][j] <dp[i]:
dp2[i] =min(dp2[i], dp[i] -dungeon[i][j])
else:
dp2[i] =1dp=dp2returndp[0]Issue: there are n planets and n teams are going to complete in the tournament which are numbered from 1 to n, the tournament is going to be hosted on the planet number n. the planets are interconnected via teleportation gateways. the team from planet i can teleport directly to planets i+distance[i] and i-distance[i], only proviede that planets with those numbers exist. one direct teleportation lasts 1 day and teleportation channels have unlimited capacity which means that at any time many teams can be passing from one planet to another. Figure out how many days before the tournament should hey leave from their home planets so they reach just in time. if there is a team which can't reach planet n, the answer for that team would be -1. Last question of problem link
Hint: find cost-of-shortest-path-in-dag-using-one-pass-of-bellman-ford. set N-1 as the source and perform top sort from there. blog
importsysclassEdge:
def__init__(self, source, dest, weight):
self.source=sourceself.dest=destself.weight=weightclassGraph:
def__init__(self, edges, N):
self.adjList= [[] for_inrange(N)]
foredgeinedges:
self.adjList[edge.source].append(edge)
defDFS(graph, v, discovered, departure, time):
discovered[v] =Trueforedgeingraph.adjList[v]:
u=edge.destifnotdiscovered[u]:
time=DFS(graph, u, discovered, departure, time)
departure[time] =vtime=time+1returntimedeffindShortestDistance(graph, source, N):
departure= [-1] *Ndiscovered= [False] *Ntime=0foriinrange(N):
ifnotdiscovered[i]:
time=DFS(graph, i, discovered, departure, time)
cost= [sys.maxsize] *Ncost[source] =0foriinreversed(range(N)):
v=departure[i]
foreingraph.adjList[v]:
u=e.destw=e.weightifcost[v] !=sys.maxsizeandcost[v] +w<cost[u]:
cost[u] =cost[v] +wresult= []
foriinrange(N-1):
ifcost[i] ==sys.maxsize: result.append(-1)
else: result.append(cost[i])
returnresultif__name__=='__main__':
N=int(input())
distance= []
for_inrange(N): distance.append(int(input()))
edges= []
foriinrange(N):
ifi+distance[i] <N:
edges.append((Edge(i+distance[i], i, 1)))
ifi-distance[i] >=0:
edges.append((Edge(i-distance[i], i, 1)))
graph=Graph(edges, N)
source=N-1res=findShortestDistance(graph, source, N)
res.append(0)
print(res)Issue: problem link
Hint: Consider everything in a form of array, let's take (0,0,0,0,0,0) and let's say M is for monitored index and C is for index with camera installed. The best combination will be (M,C,M,M,C,M). Hence, we just need to keep track of a node beeing monitored or not. Also take care of the corner case in which root node is monitored or not. refer this video
Implementation
# 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 = rightclassSolution:
defminCameraCover(self, root: Optional[TreeNode]) ->int:
self.ans=0defdfs(node):
ifnotnode:
returnFalse, Truec1,m1=dfs(node.left)
c2,m2=dfs(node.right)
cam, monitor=False, Falseifc1orc2:
monitor=Trueifnotm1ornotm2:
cam=Trueself.ans+=1monitor=Truereturncam, monitorcam, mon=dfs(root)
ifnotmon: returnself.ans+1else: returnself.ansIssue: problem link
Hint: if the largest rectangle contains at least 1 bar in full then, if we find areas of all largest rectangle for each bar included full then we can find the max rectangle area. thus, we just need to find the largest rectangle including each bar one by one and take the max of all the max areas for each bar. refer this video
Implementation
# Brute Force methodclassSolution:
deflargestRectangleArea(self, heights: List[int]) ->int:
area= []
n=len(heights)
foriinrange(n):
l=0r=0forjinrange(i-1, -1, -1):
ifheights[j] <heights[i]:
breakl-=1forkinrange(i+1, n):
ifheights[k] <heights[i]:
breakr+=1a= (r-l+1)*heights[i]
area.append(a)
returnmax(area)
# but this solution is not optimal as its time complexity is O(N^2)# Better Approach using stackclassSolution:
deflargestRectangleArea(self, heights: List[int]) ->int:
n=len(heights) # next smaller right sidedefsr(heights,n):
stack=[0]
ans=[n] *nforiinrange(1,n):
whilestackandheights[stack[-1]]>=heights[i]:
x=stack.pop()
ans[x]=istack.append(i)
returnans# next smaller left sidedefsl(heights,n):
stack=[n-1]
ans=[-1] *nforiinrange(n-2,-1,-1):
whilestackandheights[stack[-1]]>heights[i]:
x=stack.pop()
ans[x]=istack.append(i)
returnansla=sl(heights,n)
ra=sr(heights,n)
width=[]
foriinrange(n):
width.append(ra[i]-la[i]-1)
ans=0foriinrange(n):
ans=max(ans,width[i]*heights[i])
returnansIssue: maximum coins you can collect by bursting the balloons in nums[i - 1] * nums[i] * nums[i + 1]problem link
Hint: Think of a sub-problem. Break the problem into left and right portions and make a dynamic programming.
num[left-1]*val*num[right+1] + dp[i+1][right] + dp[left][i-1]. Refer this video
Implementation
Issue: max profit in overlapping intervals. problem link
Hint: use sort and binary search to reduce the time complexity to O(NlogN)
Implementation
classSolution:
defjobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) ->int:
N=len(startTime)
jobs=list(zip(startTime, endTime, profit))
jobs.sort()
startTime.sort()
@lru_cache(None)defrec(i):
ifi==N: return0j=bisect_left(startTime, jobs[i][1])
returnmax(jobs[i][2]+rec(j), rec(i+1))
returnrec(0)Issue: search a lists of words in a grid. problem link
Hint: use DFS similar to problem #1
Implementation
### DFS ApproachclassSolution:
deffindWords(self, board: List[List[str]], words: List[str]) ->List[str]:
ifnotboardornotwords: returnFalsetraced=set()
defdfs(start, i, j, traced):
dirs= [(0,1), (1,0), (-1,0), (0,-1)]
print(start)
fordx, dyindirs:
new_x=i+dxnew_y=j+dyif0<=new_x<len(board) and0<=new_y<len(board[0]) and (new_x,new_y) notintracedandboard[new_x][new_y] ==word[start]:
ifstart==len(word)-1: returnTruetraced.add((new_x, new_y))
ifdfs(start+1, new_x, new_y, traced): returnTrueelse: traced.remove((new_x, new_y))
returnls= []
forwordinwords:
start=0foriinrange(len(board)):
forjinrange(len(board[0])):
traced=set()
ifboard[i][j] ==word[start]: traced.add((i,j))
ifstart==len(word) -1:
ls.append(word)
continueifdfs(start+1, i, j, traced): ls.append(word)
final= []
foriinls:
ifinotinfinal:
final.append(i)
returnfinal# we can improve this code by optmizing DFS using **hash maps**, as we will be able te reduce the DFS start point to initiate a search# TRIE + DFS ApproachclassTrieNode:
def__init__(self):
self.children= [None] *26self.end=FalseclassSolution:
deffindWords(self, board: List[List[str]], words: List[str]) ->List[str]:
self.maxWords=len(words)
# Create Trie rootself.root=TrieNode()
# Add words to Trieforwordinwords:
self.add(word)
self.res=set()
self.r=len(board)
ifself.r==0:
returnlist(res)
self.c=len(board[0])
ifself.c==0:
returnlist(res)
self.visited= [[False] *self.cfor_inrange(self.r)]
foriinrange(self.r):
forjinrange(self.c):
idx=ord(board[i][j]) -97ifself.root.children[idx]:
self.visited[i][j] =Trueself.dfs(board, i, j, board[i][j], self.root.children[idx])
self.visited[i][j] =Falsereturnlist(self.res)
defdfs(self, board, i, j, path, trieNode):
iftrieNode.end:
self.res.add(path)
iflen(self.res) ==self.maxWords:
returnforx,yin [(-1, 0), (1, 0), (0, -1), (0, 1)]:
x_1, y_1=i+x, j+yifself.isValid(x_1, y_1):
idx=ord(board[x_1][y_1]) -97iftrieNode.children[idx]:
self.visited[x_1][y_1] =Trueself.dfs(board, x_1, y_1, path+board[x_1][y_1], trieNode.children[idx])
self.visited[x_1][y_1] =FalsedefisValid(self, i, j):
returni>=0andj>=0andi<self.randj<self.candnotself.visited[i][j]
defadd(self, word):
tmp=self.rootforwinword:
c=ord(w) -97ifnottmp.children[c]:
tmp.children[c] =TrieNode()
tmp=tmp.children[c]
tmp.end=TrueNOTE: bothTRIE+DFSandHM+DFSwillhavesametimecomplexityIssue: problem link
Hint: use BFS to explore through the entire grid
Implementation
classSolution:
deforangesRotting(self, grid: List[List[int]]) ->int:
visit, curr=set(), deque()
foriinrange(len(grid)):
forjinrange(len(grid[0])):
ifgrid[i][j] ==1:
visit.add((i, j))
elifgrid[i][j] ==2:
curr.append((i, j))
result=0whilevisitandcurr:
for_inrange(len(curr)):
i, j=curr.popleft() forcoordin ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):
ifcoordinvisit: visit.remove(coord)
curr.append(coord)
result+=1return-1ifvisitelseresultIssue: pick max of 3 stones to win the game given optimal step chosen problem link
Hint: use DP. refer to this video
Implementation
# recursive solutionclassSolution:
defstoneGameIII(self, stoneValue: List[int]) ->str:
defrec(stone, i):
ifi>=len(stone): return0ans=-math.infans=max(ans, stone[i] -rec(stone, i+1))
ifi+1<len(stone): ans=max(ans, stone[i]+stone[i+1] -rec(stone, i+2))
ifi+2<len(stone): ans=max(ans, stone[i]+stone[i+1]+stone[i+2] -rec(stone, i+3))
returnansstones=rec(stoneValue, 0)
ifstones>0: return"Alice"ifstones==0: return"Tie"return"Bob"# dynamic programming approaches# 1. top down (memoization) approach classSolution:
defstoneGameIII(self, stoneValue: List[int]) ->str:
defrec(stone, i):
ifi>=len(stone): return0ifdp[i]!=-1: returndp[i]
ans=-math.infans=max(ans, stone[i] -rec(stone, i+1))
ifi+1<len(stone): ans=max(ans, stone[i]+stone[i+1] -rec(stone, i+2))
ifi+2<len(stone): ans=max(ans, stone[i]+stone[i+1]+stone[i+2] -rec(stone, i+3))
dp[i] =ansreturndp[i] dp= [-1]*50000stones=rec(stoneValue, 0)
ifstones>0: return"Alice"ifstones==0: return"Tie"return"Bob"# 2. bottom up (tabulation approach) (Fastest)classSolution:
defstoneGameIII(self, stoneValue: List[int]) ->str:
n=len(stoneValue)
stoneValue+= [0, 0, 0]
dp= [0] * (n+3)
foriinrange(n)[::-1]:
x=stoneValue[i]
y=x+stoneValue[i+1]
z=y+stoneValue[i+2]
dp[i] =max(x-dp[i+1], y-dp[i+2], z-dp[i+3])
ifdp[0] >0: return'Alice'ifdp[0] <0: return'Bob'return'Tie'Issue: minimum path covered problem link
Hint: Use DP: MinCost(i,j) = min(MinCost(i-1,j),MinCost(i,j-1)) + Cost[i][j]
Implementation
classSolution:
defminPathSum(self, grid: List[List[int]]) ->int:
minCost= [[0for_inrange(len(grid[0]))] for_inrange(len(grid))]
minCost[0][0] =grid[0][0]
foriinrange(1, len(grid)):
minCost[i][0] =minCost[i-1][0] +grid[i][0]
forjinrange(1, len(grid[0])):
minCost[0][j] =minCost[0][j-1] +grid[0][j]
foriinrange(1, len(grid)):
forjinrange(1, len(grid[0])):
minCost[i][j] =min(minCost[i-1][j], minCost[i][j-1]) +grid[i][j]
returnminCost[len(grid)-1][len(grid[0])-1]Issue: path with obstacles problem link
Hint: Use DP
Implementation
classSolution:
defuniquePathsWithObstacles(self, grid: List[List[int]]) ->int:
ifgrid[0][0] ==1: return0numWays= [[Nonefor_inrange(len(grid[0]))] for_inrange(len(grid))]
foriinrange(len(grid)):
forjinrange(len(grid[0])):
ifgrid[i][j] ==1: numWays[i][j] =0elifi==0andj==0: numWays[i][j] =1elifi==0: numWays[i][j] =numWays[i][j-1]
elifj==0: numWays[i][j] =numWays[i-1][j]
else: numWays[i][j] =numWays[i][j-1] +numWays[i-1][j]
returnnumWays[-1][-1]Issue: number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once. problem link
Hint: Use DFS
Implementation
classSolution:
defuniquePathsIII(self, grid: List[List[int]]) ->int:
non_obstacle=0forrowingrid:
non_obstacle+=row.count(0)
self.ans=0R=len(grid)
C=len(grid[0])
start_x,start_y=(0,0)
foriinrange(R):
forjinrange(C):
ifgrid[i][j]==1:
start_x,start_y=(i,j)
breakdefhelper(r,c,count):
if0<=r<Rand0<=c<Candgrid[r][c]>=0:
ifgrid[r][c]==2:
#if we reach at 2 we will check if we have covered all non-obstacleifcount==non_obstacle+1:
self.ans+=1return# replacing current grid[i][j] by some other number so that we don't come back at this during recursiontemp=grid[r][c]
grid[r][c]=-2fornr,ncin [(1,0),(0,1),(0,-1),(-1,0)]:
helper(nr+r,nc+c,count+1)
grid[r][c]=temphelper(start_x,start_y,0)
returnself.ansIssue: problem link
Hint: Think in reverse; instead of finding the minimum prefix + suffix, find the maximum subarray. Basically find the maximum length of subarray having sum equal to sum of original array - x. To so this, use sliding window approach.
Implementation
classSolution:
defminOperations(self, nums: List[int], x: int) ->int:
arrSum=sum(nums)
maxLen=-math.infcurrSum=0target=arrSum-xi=0forjinrange(0, len(nums)):
currSum+=nums[j]
whilecurrSum>targetandi<=j:
currSum-=nums[i]
i+=1ifcurrSum==target:
maxLen=max(maxLen, j-i+1)
ifmaxLen==-math.inf: return-1else: returnlen(nums) -maxLenIssue: problem link
Hint: Use BFS
Implementation
defminimumMoves(grid, startX, startY, goalX, goalY):
ifnotgrid: return0queue=deque()
rows=len(grid)
cols=len(grid[0])
directions=[(1,0),(-1,0),(0,-1),(0,1)]
queue.appendleft((startX,startY,0))
visited=set()
whilequeue:
(i,j,dist) =queue.pop()
new_dist=dist+1fordindirections:
new_i=i+d[0]
new_j=j+d[1]
while0<=new_i<rowsand0<=new_j<colsandgrid[new_i][new_j]!='X':
if (new_i, new_j) == (goalX, goalY):
returnnew_distelif (new_i, new_j) notinvisited:
queue.appendleft((new_i,new_j,new_dist))
visited.add((new_i,new_j))
new_i+=d[0]
new_j+=d[1]Issue: Find the index of the word in the dictionary with given prefix and suffix
Hint: Use the idea of hash maps
Implementation
# Naive ApproachclassWordFilter:
def__init__(self, words: List[str]):
self.words=wordsdeff(self, prefix: str, suffix: str) ->int:
ans= []
forwordinself.words:
ifword.startswith(prefix) andword.endswith(suffix):
ans.append(self.words.index(word))
returnans[-1]
# Optimised approach using hash mapsclassWordFilter:
def__init__(self, words: List[str]):
prefixes=defaultdict(set)
suffixes=defaultdict(set)
indices=defaultdict(int)
# Storing Indicesforind, wordinenumerate(words):
indices[word] =indprefix=""suffix=""# Storing all prefixesforcharinword:
prefix+=charprefixes[prefix].add(word)
#Storing all suffixesforcharinword[::-1]:
suffix=char+suffixsuffixes[suffix].add(word)
self.prefixes=prefixesself.suffixes=suffixesself.indices=indicesdeff(self, prefix: str, suffix: str) ->int:
prefixes=self.prefixessuffixes=self.suffixesindices=self.indices# intersection of prefixes[prefix] and suffixes[suffix]common_words=prefixes[prefix] &suffixes[suffix]
max_index=-1forwordincommon_words:
max_index=max(max_index, indices[word])
returnmax_index# Your WordFilter object will be instantiated and called as such:# obj = WordFilter(words)# param_1 = obj.f(prefix,suffix)Issue: How to solve with cooldown condition imposed. problem link
Hint: One easy approach will be to use recursion but that will increase oue time complexity to O(2^N). A better approach will be to define 3 different states when we have our stocks in hand, when we don't have any stock and when we want to sell that. There will be certain possibilites to arrive at these states from previous day. For example: we can come to no stocks in hand if the previous day, we sell any stock or we don't have any stock the last day as well. we will take the max of these two. Basically build a state transition diagram. Now, at the end we will just compare the last element of the no stock and sell arrays to find out the maximum profit we can generate. Refer this video for better understanding.
NOTE: this problem can be solved by valley-peak approach if there is no cooldown period. we just need to find out the local minima and maxima and find out the difference between those to find out the max period. problem link
Implementation
classSolution:
defmaxProfit(self, prices: List[int]) ->int:
iflen(prices) <=1: return0n=len(prices)
noStock, inHand, sold= [0]*n, [0]*n, [0]*nnoStock[0] =0inHand[0] =-prices[0]
sold[0] =0foriinrange(1, n):
noStock[i] =max(noStock[i-1], sold[i-1])
inHand[i] =max(inHand[i-1], noStock[i-1]-prices[i])
sold[i] =inHand[i] +prices[i]
returnmax(noStock[n-1], sold[n-1])Issue: only 2 transactions allowed. problem link
Hint: Use divide and conquer approach. divide the array in two parts and find individual local minima and maxima. refer this video
Implementation
classSolution:
defmaxProfit(self, prices: List[int]) ->int:
n=len(prices)
ifn==0: return0left= [0]*nright= [0]*nl_min=prices[0]
r_max=prices[n-1]
foriinrange(1, n):
left[i] =max(left[i-1], prices[i]-l_min)
l_min=min(l_min, prices[i])
foriinrange(n-2, -1, -1):
right[i] =max(right[i+1], r_max-prices[i])
r_max=max(r_max, prices[i])
profit=right[0]
foriinrange(1, n):
profit=max(profit, left[i-1]+right[i])
returnprofitIssue: Problem link
Hint: Bellman-Ford algorithm
Implementation
classGraph:
def__init__(self, vertices):
self.V=verticesself.graph= []
defaddEdge(self, u, v, w):
self.graph.append([u, v, w])
defshortest_distance(self,src,dest):
dist= [float("Inf")] *self.Vdist[src] =0for_inrange(self.V-1):
foru, v, winself.graph:
ifdist[u] !=float("Inf") anddist[u] +w<dist[v]:
dist[v] =dist[u] +wifdist[dest] ==float("Inf"): print(-1)
else: print(dist[dest])
if__name__=='__main__':
road_nodes, road_edges=map(int, input().rstrip().split())
g=Graph(road_edges)
road_from= [0] *road_edgesroad_to= [0] *road_edgesroad_weight= [0] *road_edgesforiinrange(road_edges):
road_from[i], road_to[i], road_weight[i] =map(int, input().rstrip().split())
g.addEdge(road_from[i], road_to[i], road_weight[i])
q=int(input().strip())
forq_itrinrange(q):
first_multiple_input=input().rstrip().split()
x=int(first_multiple_input[0])
y=int(first_multiple_input[1])
g.shortest_distance(x,y)Issue: problem link
Hints:
Implementation
Issue: reduce time complecity of cyclic shift. problem link
Hints:
rotate only if (i)th element is '1' and (i-1)th element is not '1'. this will always result in max possible number and no of shifts can also be reduced
find out the period of the string using KMP algorithm. create a pi table and period = len(string) - pi[n-1].
Implementation
'''# Sample code to perform I/O:name = input() # Reading input from STDINprint('Hi, %s.' % name) # Writing output to STDOUT# Warning: Printing unwanted or ill-formatted data to output will cause the test cases to fail'''T=int(input())
for_inrange(T):
N,K=map(int, input().split())
A=input()
B=Ai=1x=Nwhilei<N:
s=''ifA[i] =='1'andA[i-1] !='1':
s=A[i:N] +A[0:i]
ifs>B:
B=sx=ii+=1# KMP algorithm can be used to find out period of string# generate pi table pi= [0for_inrange(N)]
foriinrange(1, N):
j=pi[i-1]
whilej>0andB[i] !=B[j]:
j=pi[j-1]
ifB[i] ==B[j]:
j+=1pi[i] =jperiod=N-pi[N-1]
ans= (K-1)*period+1*xifx==N: print((K-1)*period)
else: print(ans)Issue: Sum of submatrix. solve efficiently
Hint: Use the idea of prefix sum[DP]
Implementation
classNumMatrix:
def__init__(self, matrix: List[List[int]]):
self.dp=[[0] * (len(matrix[0])+1) for_inrange(len(matrix)+1)]
# calculate prefix sumforrinrange(len(self.dp)-1):
forcinrange(len(self.dp[0])-1):
self.dp[r+1][c+1]=matrix[r][c] +self.dp[r][c+1] +self.dp[r+1][c] -self.dp[r][c]
defsumRegion(self, row1: int, col1: int, row2: int, col2: int) ->int:
returnself.dp[row2+1][col2+1] -self.dp[row1][col2+1] -self.dp[row2+1][col1] +self.dp[row1][col1]Issue: find out the largest Prime Number possible from a subsequence of a Binary String
Hint: find out all the subsequences and store if their int form is prime
Implementation
arr= []
defisPrime(x):
ifx<=1: returnFalseforiinrange(2, x+1):
ifi*i>x: breakifx%i==0: returnFalsereturnTrue# obtaining all substringsdefsubsequence(input, output):
iflen(input) ==0:
ifoutput!=''andisPrime(int(output,2)):
arr.append(output)
returnsubsequence(input[1:], output+input[0])
subsequence(input[1:], output)
if__name__=='__main__':
s=input()
out=""subsequence(s, out)
max_=0foriinarr:
max_=max(max_, int(i,2))
ifmax_<=1: print(-1)
else: print(max_)Issue: Problem link
Hint: Use DFS
Implementation
classSolution:
defmaxPathSum(self, root: TreeNode) ->int:
self.ans=float(-inf)
defdfs(root):
ifnotroot: return0self.ans=max(self.ans, dfs(root.left)+dfs(root.right)+root.val) returnmax(0, root.val+max(dfs(root.left),dfs(root.right))) # check whether the left or part returns max sum dfs(root)
returnself.ansIssue: Removing obstacles. Problem Link
Hint: Use Breadth First Search algorithm. video for reference
Implementation
classSolution:
defshortestPath(self, grid: List[List[int]], k: int) ->int:
q=deque()
m=len(grid)
n=len(grid[0])
directions=[(1,0),(-1,0),(0,-1),(0,1)]
q.append((0,0,k))
visited=set()
visited.add((0,0,k))
ans=0whileq:
forvinrange(len(q)):
i,j,limit=q.popleft()
ifi==m-1andj==n-1:
returnansfordindirections:
new_i=i+d[0]
new_j=j+d[1]
if0<=new_i<mand0<=new_j<n:
ifgrid[new_i][new_j]==0and (new_i,new_j,limit) notinvisited:
q.append((new_i,new_j,limit))
visited.add((new_i,new_j,limit))
eliflimit>0and (new_i,new_j,limit-1) notinvisited:
q.append((new_i,new_j,limit-1))
visited.add((new_i,new_j,limit-1))
ans+=1return-1Issue: Find out an optimal solution using dynamic programming. Problem link
Hint: Use memoization or tabulation. video for reference
Implementation
classSolution:
deflengthOfLIS(self, nums: List[int]) ->int:
L= [1]*len(nums)
foriinrange(1, len(nums)):
forjinrange(i):
ifnums[j] <nums[i] andL[i] <L[j]+1:
L[i] =L[j]+1max_=0foriinrange(len(nums)):
max_=max(max_, L[i])
returnmax_Future work: Above implementation takes O(N*N) time complexity, reduce it O(NlogN). Refer this link
Issue: Solve it efficiently using dynammic programming in O(mn) complexity. Problem link
Hint: Refer to this blog or this video
Implementation
classSolution:
deflongestCommonSubsequence(self, text1: str, text2: str) ->int:
m=len(text1)
n=len(text2)
dp= [[0forxinrange(n+1)] forxinrange(m+1)]
foriinrange(m+1):
forjinrange(n+1):
ifi==0orj==0:
dp[i][j] =0eliftext1[i-1] ==text2[j-1]:
dp[i][j] =dp[i-1][j-1] +1else:
dp[i][j] =max(dp[i][j-1], dp[i-1][j])
returndp[-1][-1]❗❗❗
Issue: Problem link
Hint: no clue how to pass all the test cases
Implemenation
defsortedSubsegments(k, a, queries):
# Write your code herefori,jinqueries:
a=a[:i]+sorted(a[i:j+1])+a[j+1:]
returna[k]
# this dumb solution can only pass 10 cases, think of some better approachIssue: How to take different steps in search based on priority order. Problem link
Hint: no idea currently, need to solve it :(
Implementation
Issue: Problem link
Hint: Think in lines of prefix sum
Implementation
defarrayManipulation(n, queries):
# Write your code herearr= [0]*nforiinrange(len(queries)):
arr=arr[:(queries[i][0]-1)] + [sum(x) forxinzip([queries[i][2]]*(queries[i][1]+1-queries[i][0]), arr[queries[i][0]-1:queries[i][1]])] +arr[queries[i][1]:]
returnmax(arr)
# this solution is not optimal and runtime is exceeding, a better approach can be followed by using the concept of prefix sumdefarrayManipulation(n, queries):
# Write your code herearr= [0]*(n+2)
fori,j,kinqueries:
arr[i] +=karr[j+1] -=kmax_=temp=0forvalinarr:
temp+=valmax_=max(max_, temp)
returnmax_Issue: Problem link
Hint: sort and store the overlapping intervals
Implementation
classSolution:
defmerge(self, intervals: List[List[int]]) ->List[List[int]]:
intervals=sorted(intervals)
output=intervals[0]
res=[]
foriinrange(1,len(intervals)):
ifintervals[i][0]<=output[1]:
output[1]=max(output[1],intervals[i][1]) else:
res.append(output.copy())
output[0]=intervals[i][0]
output[1]=intervals[i][1]
res.append(output)
returnresIssue: Problem link
Hint: create counter dictionary and anagrams pairs can be found by sorting the substring
Implementation
defsherlockAndAnagrams(s):
dictionary= {}
foriinrange(len(s)):
forjinrange(i,len(s)):
substr=''.join(sorted(s[i:j+1]))
dictionary.setdefault(substr, 0)
dictionary[substr] +=1count=0forstringindictionary:
count+=sum([iforiinrange(dictionary[string])])
returncountIssue: Formatting the chosen letters. Problem Link
Hint: Think of 1. How many words we need to form each line. 2. How many spaces we should insert between two words.
Implementation
classSolution(object):
deffullJustify(self, words, maxWidth):
''' :type words: List[str] :type maxWidth: int :rtype: List[str] '''n=len(words)
L=maxWidthi=0# the index of the current word ans= [] defgetKwords(i):
k=0# figure out how many words can fit into a linel=' '.join(words[i:i+k]) whilelen(l) <=Landi+k<=n:
k+=1l=' '.join(words[i:i+k])
k-=1returnkdefinsertSpace(i, k):
''' concatenate words[i:i+k] into one line'''l=' '.join(words[i:i+k]) ifk==1ori+k==n: # if the line contains only one word or it is the last line spaces=L-len(l) # we just need to left assigned itline=l+' '*spaceselse: spaces=L-len(l) + (k-1) # total number of spaces we need insert space=spaces// (k-1) # average number of spaces we should insert between two wordsleft=spaces% (k-1) # number of 'left' words, i.e. words that have 1 more space than the other words on the right sideifleft>0:
line= ( " "* (space+1) ).join(words[i:i+left]) # left wordsline+=" "* (space+1) # spaces between left words & right wordsline+= (" "*space).join(words[i+left:i+k]) # right woredselse: line= (" "*space).join(words[i:i+k])
returnlinewhilei<n: k=getKwords(i) line=insertSpace(i, k) # create a line which contains words from words[i] to words[i+k-1]ans.append(line) i+=kreturnansIssue: To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above. Problem link
Hint: For recursive solution, take either only the first or first two digits of the given number and recurse through the rest in a similar manner.
Implementation
recursive
classSolution:
defnumDecodings(self, s: str) ->int:
ifs[0] =="0": return0returnself.sub(s)
defsub(self,string):
ifnotstring:
return1first=second=0if1<=int(string[:1]) <=9:
first=self.sub(string[1:])
if10<=int(string[:2]) <=26:
second=self.sub(string[2:])
returnfirst+seconddynamic programming
classSolution:
defnumDecodings(self, s: str) ->int: ifs[0] =="0": return0dp= [1] * (len(s) +1)
foriinrange(2, len(s) +1):
dp[i] = (dp[i-1] if1<=int(s[i-1]) <=9else0) + (dp[i-2] if10<=int(s[i-2] +s[i-1]) <=26else0)
returndp[-1] Issue: Minimize time complexity and solve using DP and binary search. Problem link
Hint: Use the logic of LIS. Also, go through this bisect library which is used to find a position in list where an element needs to be inserted to keep the list sorted
Implementation
classSolution:
defmaxEnvelopes(self, envelopes: List[List[int]]) ->int:
# For each envelope, sorted by envelope[0] first, so envelope[1] is the the longest# increasing sequence(LIS) problem. When envelope[0] tie, we reverse sort by envelope[1]# because bigger envelope[1] can't contain the previous one.envelopes.sort(key=lambdae: (e[0], -e[1]))
# dp keeps some of the visited element in a sorted list, and its size is length Of LIS# so far. It always keeps the our best chance to build a LIS in the future.dp= []
forenvelopeinenvelopes:
i=bisect.bisect_left(dp, envelope[1])
ifi==len(dp):
# If envelope[1] is the biggest, we should add it into the end of dp.dp.append(envelope[1])
else:
# If envelope[1] is not the biggest, we should keep it in dp and replace the# previous envelope[1] in this position. Because even if envelope[1] can't build# longer LIS directly, it can help build a smaller dp, and we will have the best# chance to build a LIS in the future. All elements before this position will be# the best(smallest) LIS sor far. dp[i] =envelope[1]
# dp doesn't keep LIS, and only keep the length Of LIS.returnlen(dp)Issue: link
Hint:Store the matrices diagonal in collections.defaultdict(list) and sort them
Implementation
classSolution:
defdiagonalSort(self, mat: List[List[int]]) ->List[List[int]]:
dict=collections.defaultdict(list)
n=len(mat)
m=len(mat[0])
foriinrange(0,n):
forjinrange(0,m):
dict[n-1-i+j].append(mat[i][j])
foriindict:
dict[i].sort()
ans=[[0foriinrange(0,m)] foriinrange(0,n)]
foriinrange(0,n):
forjinrange(0,m):
print(dict[n-1-i+j])
ans[i][j]=dict[n-1-i+j][0]
dict[n-1-i+j].pop(0)
returnansIssue: linked lists and have to return as a linked list. link
Hint: Decode and encode linked list
Implementation
classSolution:
defmergeKLists(self, lists: List[ListNode]) ->ListNode:
defhelper(node):
nodes= []
whilenode: nodes.append(node)
node=node.nextreturnnodesnodes= []
fornodeinlists:
nodes.extend(helper(node))
ifnotnodes:
return# print(nodes)# print(type(nodes))nodes.sort(key=lambdax: x.val)
fornode1, node2inzip(nodes, nodes[1:]):
node1.next=node2nodes[-1].next=Nonereturnnodes[0]Issue: Converting back to list and then retracing back exceeded the time limit. link
Hint: Just check the head and node.next of where we want to add the LL
Implementation
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:
defmergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) ->ListNode:
prev=head=ListNode(0, list1) # Sentinal node for edge a=1for_inrange(a): # Reach node before lefthead=head.nexttemp=headfor_inrange(b-a+1): # Reach right nodehead=head.nexttemp.next=list2# Add newlist at leftwhilelist2.next: # Traverse the new listlist2=list2.nextlist2.next=head.next# Add nodes after right nodereturnprev.nextIssue: reduce time complexity using DP. link
Hint: Maintain a new 2d array of zeros and update whenever you sth common.
Implementation
classSolution:
deffindLength(self, nums1: List[int], nums2: List[int]) ->int:
dp= [[0foriinrange(len(nums1) +1)] foriinrange(len(nums2) +1)]
foriinrange(len(nums1)-1,-1,-1):
forjinrange(len(nums2)-1,-1,-1):
ifnums1[i] ==nums2[j]:
dp[j][i] =dp[j+1][i+1] +1num=0foriindp:
forjini:
num=max(num,j)
returnnumIssue: reduce the complexity. link
Hint: 4Sum = 1+3Sum 🙃. then use 2 pointer approach in 3Sum.
Implementation
classSolution:
deffourSum(self, nums: List[int], target: int) ->List[List[int]]:
res= []
nums.sort()
foriinrange(len(nums)):
ifi==0ornums[i] >nums[i-1]:
diff=target-nums[i]
threeSums=self.threeSum(nums[i+1:], diff)
forthreeSuminthreeSums:
res.append([nums[i]] +threeSum)
returnresdefthreeSum(self, nums, target):
res= []
iflen(nums) <3: returnresforiinrange(len(nums) -2):
ifi>0andnums[i] ==nums[i-1]: continuel, r=i+1, len(nums) -1whilel<r :
s=nums[i] +nums[l] +nums[r]
ifs==target:
res.append([nums[i] ,nums[l] ,nums[r]])
l+=1; r-=1whilel<randnums[l] ==nums[l-1]: l+=1whilel<randnums[r] ==nums[r+1]: r-=1elifs<target :
l+=1else:
r-=1returnresIssue: maintain the same order problem link
Hint: look for the point where we can cut the LL and how to retreive the other parts
Implementation
classNode:
def__init__(self, data):
self.data=dataself.next=NonedefisVowel(x):
return (x=='a'orx=='e'orx=='i'orx=='o'orx=='u'orx=='A'orx=='E'orx=='I'orx=='O'orx=='U')
classLinkedList:
def__init__(self):
self.head=Nonedefpush(self, new_data):
new_node=Node(new_data)
new_node.next=self.headself.head=new_nodedefprintList(self):
temp=self.headwhile (temp):
print (temp.data)
temp=temp.nextdefarrange(self,head):
new=self.headlatest_vowel=Nonecurr=self.headifself.head==None: returnNoneifisVowel(self.head.data):
latest_vowel=self.headelse:
whilecurr.next!=NoneandnotisVowel(self.head.data):
curr=curr.nextifcurr.next==None: returnself.headlatest_vowel=new=curr.nextcurr.next=curr.next.nextlatest_vowel.next=self.headwhilecurr!=Noneandcurr.next!=None:
ifisVowel(curr.next.data):
ifcurr==latest_vowel:
latest_vowel=curr=curr.nextelse:
temp=latest_vowel.nextlatest_vowel.next=curr.nextlatest_vowel=latest_vowel.nextcurr.next=curr.next.nextlatest_vowel.next=tempelse:
curr=curr.nextreturnnewls= ['a','b','c','e','d','o','x','i']
llist=LinkedList()
foriinls[::-1]:
llist.push(i)
llist.arrange(llist)
llist.printList()Issue: Numbers are stored in linked lists, so how to access them properly. link
Hint: Convert nodes to a list and then back to linked list.
Implementation
# Definition for singly-linked list.classListNode:
def__init__(self, val=0, next=None):
self.val=valself.next=nextclassSolution:
defnode_to_list(self, listnode):
l=[]
whileTrue:
l.append(listnode.val)
iflistnode.next!=None:
listnode=listnode.nextelse:
returnldeflist_to_LL(self,arr):
iflen(arr) <1:
returnNoneiflen(arr) ==1:
returnListNode(arr[0])
returnListNode(arr[0], next=self.list_to_LL(arr[1:]))
defreverseList(head: ListNode) ->ListNode:
prev=Nonewhilehead:
next_node=head.nexthead.next=prevprev=headhead=next_nodereturnprevdefaddTwoNumbers(self, l1: ListNode, l2: ListNode) ->ListNode:
l1=self.node_to_list(l1)
l2=self.node_to_list(l2)
num1=0num2=0foriinrange(len(l1)):
num1+=l1[i]*(10**i)
foriinrange(len(l2)):
num2+=l2[i]*(10**i)
num=num1+num2l= []
ifnum==0:
l=[0]
whilenum>0:
l.append(num%10)
num=num//10returnself.list_to_LL(l)Issue of the problem: Test whether array can be sorted by swaping three items at a time in order: ABC -> BCA -> CAB -> ABC. Link
Hint: Check out the number of inversions. The given below implementation seems to be simple but there is an awesome logic behind this. Refer to these paper's for understanding the logic behind it. Paper1 and Paper2
Implementation:
stringlarrysArray(vector<int>A) {
intn=A.size();
intsum=0;
for(inti=0; i<n; i++){
for(intj=i+1; j<n; j++){
if(A[j] <A[i]){
sum+=1;
} }
}
if(sum%2==0){
return"YES";
}
else{
return"NO";
}
} Issue of the problem: Time complexity issue in case of larger values. link
Hint: Sort the array, and then check the difference of adjacent pairs, if its less than ur last min value, update it only if the index of those pairs are in same way in original array.
Implementation:
intn;
cin>>n;
vector<double>sorted(n);
map<double, int>arr;
for (inti=0; i<n; ++i) {
doublex;
cin>>x;
sorted[i] =x;
arr[x] =i;
}
sort(sorted.begin(), sorted.end());
doublemin=INT_MAX;
for (inti=0; i<n-1; ++i) {
doublex=sorted[i+1] -sorted[i];
if (x<min) {
intfirst=arr[sorted[i]];
intsecond=arr[sorted[i+1]];
if (second<first) {
min=x;
}
}
}
cout<<long(min);Issue of the problem: link
Hint: (This hint I found in the discussion panel and is a very easy implementation of recursion).
- At any point, either we can either use that number or not.
- If we do not use it then X value will remain same.
- And if we use it, then we have to subtract pow(num, N) from X.
- num value will increase every time as we can use one number at most once.
- Our answer will be sum of both these cases. This is obvious.
- And then we will do same thing for two values of X i.e. X and X-pow(num,N).
- If value of X is less than pow(num, N) then we cannot get answer as value of num will keep increasing. Hence, we return 0.
- If it is equal to 1, then we can return 1.
Implementation:
intpowerSum(intX,intN,intnum){
if(pow(num,N)<X)
returnpowerSum(X,N,num+1)+powerSum(X-pow(num,N),N,num+1);
elseif(pow(num,N)==X)
return1;
elsereturn0;
}Issue of the problem: Large factorials can't be stored even in case of long long int. So, the given below is a idea for solving such cases.
Hint: Initialize a matrix of a large size ,let's say, 1000. Put its start value as 1 and one other parameter size as 1. Now, as you peform normal multplication update the values.
Implementation:
voidextraLongFactorials(intn) {
intval[1000];
intsize=1;
val[0] =1;
size=1;
for(inti=2; i<=n; i++){
intcarry=0;
for(intj=0; j<size; j++){
intpod=val[j]*i+carry;
val[j] =pod%10;
carry=pod/10;
}
while(carry){
val[size] =carry%10;
carry/=10;
size++;
}
}
for(inti=size-1; i>=0; i--)cout<<val[i];
}Problem: Given the queen's position and the locations of all the obstacles, find and print the number of squares the queen can attack from her position at (r_q, c_q).
Hint: Initialize the distances from the current position to the end of the chessboard in every direction to its actual distance. Then check along every direction and when any obstacle comes in front, set that distance as the value along that direction.
Implemenatation:
intqueensAttack(intn, intk, intr_q, intc_q, vector<vector<int>>obstacles) {
queen_row=r_qqueen_column=c_qtop=n-queen_rowbottom=queen_row-1right=n-queen_columnleft=queen_column-1top_left=min(n-queen_row, queen_column-1)
top_right=n-max(queen_column, queen_row)
bottom_left=min(queen_row, queen_column) -1bottom_right=min(queen_row-1, n-queen_column)
fora0inxrange(k):
obstacle_row=obstacles[a0][0]
obstacle_column=obstacles[a0][1]
ifobstacle_row==queen_row:
ifobstacle_column>queen_column:
top=min(top, obstacle_column-queen_column-1)
else:
bottom=min(bottom, queen_column-obstacle_column-1)
elifobstacle_column==queen_column:
ifobstacle_row>queen_row:
right=min(right, obstacle_row-queen_row-1)
else:
left=min(left, queen_row-obstacle_row-1)
elifabs(obstacle_column-queen_column) ==abs(obstacle_row-queen_row):
ifobstacle_column>queen_columnandobstacle_row>queen_row:
top_right=min(top_right, obstacle_column-queen_column-1)
elifobstacle_column>queen_columnandobstacle_row<queen_row:
bottom_right=min(bottom_right, obstacle_column-queen_column-1)
elifobstacle_column<queen_columnandobstacle_row>queen_row:
top_left=min(top_left, queen_column-obstacle_column-1)
elifobstacle_column<queen_columnandobstacle_row<queen_row:
bottom_left=min(bottom_left, queen_column-obstacle_column-1)
printtop+bottom+right+left+top_left+top_right+bottom_left+bottom_right }Issue of the problem: link
Hint: 1. Make a vector of capacity of every box 2. Make a vector of all the balls 3. Sort both of them
Compare both the vectors. If same then possible else impossible.
Implementation:
stringorganizingContainers(vector<vector<int>>container){
vector<int>capacity;
vector<int>balls;
for(unsignedinti=0; i<container.size(); i++){
intcols=0;
introws=0;
for(unsignedintj=0; j<container.size(); j++){
cols+=container[i][j];
rows+=container[j][i];
}
balls.push_back(cols);
capacity.push_back(rows);
} sort(balls.begin(), balls.end());
sort(capacity.begin(), capacity.end());
if(balls==capacity){
return"Possible";
}
else{
return"Impossible";
}
}Issue of the problem: Checking whether a vector can be sorted using reverse or swap operation. link
Hint: * Run through the vector from index 1 to len-2 ( leaving the first and last elements)
At each of these indices check whether it forms an inversion or a reverse inversion. Inversion is if curr > prev && curr > next. Similarly find out reverse inversions, curr < prev && curr < next. I call inversions as dips, and reverse inversions as ups. For the first and last elements you can check only the next and prev respectively as they are at the boundary.
Once you have collected data of these inversions, if you analyze you will see that if reverse has to form a soln, you will have only one dip and one up.
And if swapping can be soln then there will be 2 dips and 2 ups.
If you get more than 2 dips and 2ups, it means it can't be solved.
There are some edge cases which you need to take care of though.
A relevant you tube video to get a deeper insight of above algorithm.
Issue of the problem: link
Hint: The base of the Figure will always contribute to the total surface area of the figure. Now, to calculate the area contributed by the walls, we will take out the absolute difference between the height of two adjacent wall. The difference will be the contribution in the total surface area.
Implementation
intcontribution_height(intcurrent, intprevious) { returnabs(current-previous); }
intsurfaceArea(vector<vector<int>>A) {
intans=0; intN=A.size();
intM=A[0].size();
for (inti=0; i<N; i++) { for (intj=0; j<M; j++) {
intup=0; intleft=0; if (i>0) up=A[i-1][j]; if (j>0) left=A[i][j-1]; ans+=contribution_height(A[i][j], up) +contribution_height(A[i][j], left); if (i==N-1) ans+=A[i][j]; if (j==M-1) ans+=A[i][j]; } } //Addingthecontributionbythebaseandtopofthefigureans+=N*M*2; returnans;
}Issue: Represents the smallest lexicographically smallest permutation of natural numbers, such that |pos[i]-i|=k. link
Hint: Distribute into k and swap between 2k.
Implementation:
vector<int>absolutePermutation(intn, intk) {
vector<int>pos(n);
for(inti=0; i<n; i++){
pos[i]=i+1;
}
vector<int>permutation(n);
if(k!=0){
if(n%k!=0|| (n/k)%2!=0||k>n/2){
return {-1};
}
for(intm=0; m<n; m=m+2*k){
for(intj=0;j<k;j++){
swap(pos[m+j], pos[m+j+k]);
}
}
}
permutation=pos;
returnpermutation;
}Issue: Check whether the teams can be ranked on the basis of three parameters. link
Hint: Make a 2d vector and sort it. Then do comparisons in rows and change the bool if not possible.
Implementation:
intn;
cin>>n;
vector<vector<int>>v(n);
for (inti=0;i<n;i++)
{
inta, b, c;
cin>>a>>b>>c;
v[i].push_back(a);
v[i].push_back(b);
v[i].push_back(c);
}
sort(v.begin(), v.end());
boolans=true;
for (inti=0;i<n-1;i++){ intcount=0;
for (intj=0;j<3;j++){
if (v[i][j] <v[i+1][j])
count++;
elseif (v[i][j] >v[i+1][j])
ans=false;
}
if (count==0)
ans=false;
}
if (ans)
cout<<"Yes";
elsecout<<"No";Issue: sort the dictionary by values. link
Hint: Use counter function from collections library and then Counter(arr).most_common to sort the counter dicitonary according to the values or can use this: sorted(Counter(arr).items(), key=lambda x: x[1], reverse=True)