Please enable JavaScript.
Coggle requires JavaScript to display documents.
Coding Patterns, Coding Patterns - Coggle Diagram
Coding Patterns
P8: Trees - DFS
-
-
-
-
- Return from Recursive function
-
-
Single Root to Leaf Path and tracing back
- Deleting currentPath [-1]
- Return output from main function not recursive function
- All Paths for a Sum (medium)
-
- Sum of Path Numbers (medium)
-
- Binary Tree Path Sum (easy)
-
-
-
Algorithm
- Start DFS with the root of the tree.
- If the current node is not a leaf node, do two things:
2.2 Make two recursive calls for both the children of the current node with the new number calculated in the previous step.
2.1 Subtract the value of the current node from the given number to get a new sum => S = S - node.value
- At every step, see if the current node being visited is a leaf node and if its value is equal to the given number ‘S’. If both these conditions are true, we have found the required root-to-leaf path, therefore return true.
If the current node is a leaf but its value is not equal to the given number ‘S’, return false.
Graphs
-
-
Algorithm
G(U,V): U comes before V in the ordering.
- Source : Vertices with no incoming edges {i:[] for i in range(nodes)}
- Indegrees : Number of incoming edges {i:0 for i in range(nodes)}
-
P1 : Sliding Window
Template:
- iterate
- constraint/pattern/K/sum(S)
- output
Types
Arrays: [1,2,3,5,8],
Strings: [4,7,9,12]
Dynamic Sliding Window
- Smallest Subarray with a given sum
-
- Longest substring with K distinct characters
-
- Fruits into Basket
(Longest substring with at most 2 distinct characters)
-
Partial_Dynamic_SW
- Longest substring with same letters after replacement
-
- Longest substring with Ones after replacement
-
-
-
Standard Sliding Window
- PC1: Permutations in a String
-
-
Array_Standard SW
- Maximum Sum Subarray of Size 'K'
-
- Average Subarray of Size 'K'
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-