This function implements the binary search algorithm to efficiently find a target value within a sorted array. It repeatedly divides the search interval in half. This is a fundamental algorithm used in searching database...

Binary search operates on a sorted array by repeatedly dividing the search interval in half. It starts with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, the search narrows to the lower half. Otherwise, it narrows to the upper half. This process is repeated until the value is found or the interval is empty. The time complexity is O(log N), where N is the number of elements in the array, due to the halving of the search space in each step. The space complexity is O(1) as it uses a constant amount of extra space. Key edge cases include an empty array, a target smaller than the smallest element, a target larger than the largest element, and the target being the first or last element. The loop invariant is that if the target exists, it must be within the `arr(low:high)` subarray.

function binarySearch(arr, target): low = 0 high = length(arr) - 1 index = -1 if arr is empty: return index while low <= high: mid = low + floor((high - low) / 2) if arr[mid] == target: index = mid return index else if a...

This function calculates the factorial of a non-negative integer using recursion. The factorial of a number `n` (denoted as `n!`) is the product of all positive integers less than or equal to `n`. This recursive implemen...

The factorial function `n!` is defined as the product of all positive integers up to `n`. For `n=0`, `0!` is defined as 1. This recursive implementation directly translates this definition. The base case is `n=0`, where the function returns 1. For any `n > 0`, the function calls itself with `n-1` and multiplies the result by `n`. The time complexity is O(N) because each recursive call reduces `n` by 1 until the base case is reached, resulting in N calls. The space complexity is also O(N) due to the call stack depth required to store the intermediate function calls. An important edge case is handling negative input, for which factorial is undefined, and this implementation throws an error. The correctness relies on the base case being correctly handled and the recursive step accurately reducing the problem size.

function factorialRecursive(n): if n < 0: error 'Factorial undefined for negative numbers' else if n == 0: return 1 else: return n * factorialRecursive(n - 1)

Dijkstra's algorithm finds the shortest paths from a single source node to all other nodes in a graph with non-negative edge weights. It's a greedy algorithm that iteratively selects the unvisited node with the smallest...

Dijkstra's algorithm maintains a set of visited nodes and a distance array, initialized to infinity for all nodes except the start node (which is 0). It uses a priority queue to efficiently select the unvisited node with the smallest tentative distance. In each step, it extracts the node `u` with the minimum distance from the priority queue, marks it as visited, and then relaxes all edges `(u, v)` originating from `u`. Relaxation involves checking if the path through `u` to `v` is shorter than the current shortest path known for `v`. If so, the distance to `v` is updated, and `v` is added to the priority queue. The time complexity is typically O(E log V) or O(E + V log V) using a binary heap, where V is the number of vertices and E is the number of edges. With a Fibonacci heap, it can be O(E + V log V). Space complexity is O(V + E) for storing the graph and O(V) for the priority queue and visited set. Edge cases include disconnected graphs (unreachable nodes remain at infinity distance), graphs with only one node, and graphs with no edges.

function dijkstra(graph, startNode): numNodes = number of nodes in graph distances = array of size numNodes, initialized to infinity distances[startNode] = 0 priority_queue = empty min-priority queue add (0, startNode) t...

This function finds all occurrences of anagrams of a pattern string `p` within a larger text string `s`. It employs a sliding window technique, maintaining frequency counts of characters within the window and comparing t...

The algorithm uses a sliding window of size equal to the length of the pattern `p`. Two frequency maps (hash maps or dictionaries) are maintained: one for the pattern `p` and one for the current window in `s`. The pattern's frequency map is computed once. The window's frequency map is initialized with the first `m` characters of `s`. Then, the window slides one character at a time. For each slide, the character entering the window is added to `sFreq`, and the character leaving the window is removed. If `sFreq` becomes equal to `pFreq`, it signifies an anagram, and the starting index of the window is recorded. The time complexity is O(N), where N is the length of `s`, because each character is processed a constant number of times. The space complexity is O(K), where K is the size of the character set (e.g., 26 for lowercase English letters), for storing the frequency maps. Edge cases include an empty pattern, an empty string, or a pattern longer than the string, all of which are handled by returning an empty result or early exit.

function findAnagrams(s, p): n = length(s) m = length(p) result_indices = [] if m > n: return result_indices p_freq = map() s_freq = map() // Initialize p_freq for each char c in p: increment count of c in p_freq // Init...

This code implements a Trie (prefix tree) data structure in MATLAB, which is efficient for storing and retrieving strings based on their prefixes. It includes methods for inserting words, searching for exact word matches...

The Trie is implemented using a `TrieNode` class, where each node can have multiple children (one for each possible character) and a flag indicating if it marks the end of a word. The `insert` method traverses the Trie, creating new nodes as needed, and marks the final node for the word. The `search` method follows the path for the given word and checks the `isEndOfWord` flag. The `startsWith` method checks if a path for the prefix exists. The time complexity for insertion, search, and prefix search is O(L), where L is the length of the word or prefix, as it involves a single traversal. The space complexity depends on the number of nodes, which is proportional to the total number of characters in all inserted words. Edge cases like empty strings and non-existent prefixes are handled. The structure ensures that all prefixes of a valid word are also implicitly represented.

class TrieNode: children = map() isEndOfWord = false class Trie: root = TrieNode() function insert(word): currentNode = root for each character in word: if character not in currentNode.children: currentNode.children[char...

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted....

Bubble Sort works by making multiple passes through the array. In each pass, it compares adjacent elements and swaps them if they are in the wrong order. The largest unsorted element 'bubbles up' to its correct position at the end of the unsorted portion of the array in each pass. The time complexity is O(n^2) in the worst and average cases, where n is the number of elements, due to the nested loops. In the best case (already sorted array), it can be O(n) if an optimization flag is used to detect no swaps. The space complexity is O(1) as it sorts in-place, requiring only a constant amount of extra space for temporary variables. The algorithm is correct because each pass guarantees that at least one more element is placed in its final sorted position.

function bubbleSort(arr): n = length(arr) for i from 1 to n-1: swapped = false for j from 1 to n-i: if arr[j] > arr[j+1]: swap arr[j] and arr[j+1] swapped = true if not swapped: break return arr

Selection Sort is a simple in-place comparison sorting algorithm. It works by repeatedly selecting the smallest element from the unsorted portion of the array and moving it to the beginning of the sorted portion. This pr...

Selection Sort divides the array into two parts: a sorted prefix and an unsorted suffix. In each pass, it finds the minimum element in the unsorted suffix and swaps it with the first element of the unsorted suffix. This effectively extends the sorted prefix by one element. The time complexity is O(n^2) in all cases (best, average, and worst) because it always performs n-1 passes, and each pass involves scanning the remaining unsorted portion of the array. The space complexity is O(1) because it sorts the array in-place, using only a constant amount of extra memory for temporary variables during swaps. The algorithm is correct because each pass correctly places the next smallest element into its final sorted position.

function selectionSort(arr): n = length(arr) for i from 1 to n-1: minIndex = i for j from i+1 to n: if arr[j] < arr[minIndex]: minIndex = j if minIndex != i: swap arr[i] and arr[minIndex] return arr

This function identifies and returns the index of a peak element within a one-dimensional array. A peak element is defined as an element that is strictly greater than its immediate neighbors. This algorithm is useful in...

The algorithm uses a binary search approach to efficiently find a peak element. It leverages the property that if an element is not a peak, at least one of its neighbors must be greater, guiding the search towards a peak. The time complexity is O(log n) because the search space is halved in each iteration. The space complexity is O(1) as it only uses a few variables. Edge cases like arrays of size 1 or 2, and peaks at the array boundaries, are explicitly handled. The correctness is ensured by the binary search invariant: a peak element is guaranteed to exist within the current search interval [left, right].

function findPeakElement(nums): n = length(nums) if n == 1: return 1 if nums[0] > nums[1]: return 0 if nums[n-1] > nums[n-2]: return n-1 left = 1 right = n - 2 while left <= right: mid = floor((left + right) / 2) if nums...