Variant of two pointers approach, moving 2 pointers at different speeds
Start by placing both slow and fast pointers at the head of a linked list.
Move the slow pointer one node at a time and the fast pointer two nodes at a time.
If there is a cycle, the two pointers will eventually meet
This technique can also find the middle node of a linked list in one pass. When the fast pointer reaches the end, the slow pointer will be at the middle.
Set previous to null, set current to head of the linked list
Use a while loop to go through the list till current is null
Set next to node after current
Then reverse pointer so that current points to previous. Then move previous to current and current to next.
Example Code:
def reverse_linked_list(head): prev = None current = head while current is not None: next = current.next current.next = prev prev = current current = next return prev ## head of reversed linked list
Uses a stack to find the next greater or next smaller element in an array
Use stack to track indices of elements for which we have not found next greatest element
Initialize the result array with -1s
For each element, check if its greater than the element at the top of the stack.
If it is, pop that element and push the index of new greater element onto the stack.
If it is not, then just push index of new element onto the stack
def next_greater_element(arr): n = len(arr) stack = [] result = [-1] * n for i in range(n): while stack and arr[i] > arr[stack[-1]]: result[stack.pop()] = arr[i] stack.append(i) return result
Finding a topological order in a Directed Acyclic Graph
Counting the number of connected components in a graph
DFS can be implemented recursively, or iteratively using a stack
Here is a generic approach to solve DFS related problems:
Choose a starting point
Keep track of visited nodes to avoid cycles
Perform required operation
Explore unvisited neighbours until all nodes are visited
def dfs_recursive(self, v. visited): visited.add(v) print(v, end=' ') for neighbour in self.grah[v]: if neighbour not in visited: self.dfs_recursive(neighbour, visited)visited = set()dfs_recursive(1, visited)
Finding shortest path between 2 nodes in an unweighted graph
Printing all nodes of a tree level by level
Finding all connected components in a graph
Finding shortest transformation sequence from one word to another
def bfs(self, start): visited = set() queue = deque([start]) visited.add(start) while queue: vertex = queue.popleft() print(vertex, end = ' ') for neighbour in self.graph[vertex]: if neighbour not in visited: visited.add(neighbour) queue.append(neighbour)
Approach Explained:
Add starting node to the queue
Set up a visited set, continue as long as the queue is not empty
Problems that involve exploring all potential solution paths and backtracking the paths that do not lead to a valid solution
Problems:
Generate all possible permutations or combinations of a given set of elements
Solve puzzles like Sudoku or N-Queens Problem
Find all possible paths from start to end in a graph or a maze
Generate all valid parentheses of a given length
Example - Generate all possible subsets
We start with an empty array.
When we encounter the first element, we have a choice, we either include it in our solution or not. We take both paths and use recursion to achieve this for all elements