This function finds the longest palindromic substring within a given string. It utilizes dynamic programming to efficiently determine all palindromic substrings. A common use case is in text processing or bioinformatics...

The algorithm uses a 2D boolean array `dp` where `dp[i][j]` is true if the substring from index `i` to `j` (inclusive) is a palindrome. It initializes `dp` for single characters and then iteratively builds up solutions for longer substrings. The time complexity is O(n^2) because we fill an n x n DP table. The space complexity is also O(n^2) for the DP table. Edge cases like empty strings or strings with a single character are handled. The correctness relies on the fact that a substring is a palindrome if its inner substring is a palindrome and its outer characters match.

function longestPalindrome(s): n = length(s) if n < 2: return s dp = 2D array of size n x n, initialized to false start = 0, maxLength = 1 // Base case: single characters are palindromes for i from 0 to n-1: dp[i][i] = t...

This function finds the kth smallest element in a matrix where each row and column is sorted in ascending order. It leverages a min-heap (priority queue) to efficiently keep track of the smallest available elements. This...

The algorithm initializes a min-heap with the first element of each row. It then repeatedly extracts the minimum element from the heap and, if available, adds the next element from the same row to the heap. This process continues until the kth element is extracted. The time complexity is O(k log n), where n is the number of rows, because we perform k extractions and at most k insertions into the heap, each taking O(log n) time. The space complexity is O(n) for the heap. Edge cases include an empty matrix or k being larger than the total number of elements. The invariant is that the heap always contains the smallest unvisited element from each row that has been partially explored.

function kthSmallest(matrix, k): n = number of rows in matrix if n == 0 or matrix[0] is empty: throw error minHeap = new MinPriorityQueue() // Initialize heap with first element of each row for i from 0 to n-1: if matrix...

This function computes the sum of all integer elements within a given array. It iterates through the array, accumulating the values into a single total. This is a fundamental operation used in many data analysis and calc...

The function initializes a variable `$totalSum` to 0. It then checks if the input array `$numbers` is empty. If it is, it returns 0 immediately. Otherwise, it iterates through each element of the array using a `foreach` loop. For each element, it checks if it's an integer and, if so, adds it to `$totalSum`. The loop terminates after processing all elements. The time complexity is O(n), where n is the number of elements in the array, as each element is visited once. The space complexity is O(1) as only a few variables are used. The edge case of an empty array is handled by returning 0.

function sumArray(numbers): totalSum = 0 if numbers is empty: return 0 for each number in numbers: if number is an integer: totalSum = totalSum + number return totalSum

This function finds the maximum sum of a contiguous subarray within a given array of integers. It employs Kadane's algorithm, an efficient dynamic programming approach. This algorithm is widely used in financial analysis...

Kadane's algorithm iterates through the array, maintaining two variables: `$current_max` (the maximum sum ending at the current position) and `$max_so_far` (the overall maximum sum found so far). For each element, it updates `$current_max` by choosing between the current element itself or the current element added to the previous `$current_max`. This ensures that `$current_max` always represents the largest possible sum ending at the current index. Then, `$max_so_far` is updated if `$current_max` is greater. The time complexity is O(n) because it involves a single pass through the array. The space complexity is O(1) as it only uses a few variables. Edge cases include an empty array and an array containing only negative numbers, which are handled by initializing `$max_so_far` and `$current_max` with the first element.

function maxSubArray(nums): n = length(nums) if n == 0: throw error max_so_far = nums[0] current_max = nums[0] for i from 1 to n-1: current_max = max(nums[i], current_max + nums[i]) max_so_far = max(max_so_far, current_m...

This PHP code calculates the factorial of a non-negative integer using recursion. The factorial of a number `n` is the product of all positive integers less than or equal to `n`. For example, 5! = 5 * 4 * 3 * 2 * 1 = 120...

The `calculateFactorial` function computes n! recursively. It first checks for invalid input (negative numbers) and returns an error. The base case for the recursion is when `n` is 0, in which case it returns 1 (since 0! = 1). For any `n` greater than 0, it recursively calls itself with `n-1` and multiplies the result by `n`. The `calculateFactorialHelper` function is used to streamline the recursive calls, ensuring the negative input check is only performed once. The time complexity is O(n) because each number from n down to 1 is processed once. The space complexity is O(n) due to the recursion depth, which can lead to stack overflow for very large `n`. The invariant maintained is that `calculateFactorialHelper(k)` correctly computes k! for all `k` from 0 to `n`.

function calculateFactorial(n): if n < 0: return "Error: Negative input" if n == 0: return 1 return n * calculateFactorialHelper(n - 1) function calculateFactorialHelper(n): if n == 0: return 1 return n * calculateFactor...

This PHP code implements the Merge Sort algorithm, a highly efficient, comparison-based sorting algorithm. It works by recursively dividing the input array into smaller subarrays, sorting them, and then merging them back...

Merge Sort is a divide-and-conquer algorithm. The `mergeSort` function recursively divides the array into halves until subarrays of size 0 or 1 are reached, which are inherently sorted. The `merge` function then combines these sorted subarrays. It uses two pointers to iterate through the temporary left and right subarrays, comparing elements and placing the smaller one into the main array. The time complexity of Merge Sort is consistently O(n log n) in all cases (best, average, and worst) because the division and merging steps are always performed. The space complexity is O(n) due to the temporary arrays created during the merge step. Edge cases include empty arrays and arrays with a single element, which are handled by the base case of the recursion. The correctness relies on the invariant that `merge` always produces a sorted subarray from two sorted input subarrays.

function mergeSort(array, left, right): if left >= right: return mid = floor((left + right) / 2) mergeSort(array, left, mid) mergeSort(array, mid + 1, right) merge(array, left, mid, right) function merge(array, left, mid...

This PHP code defines a `TreeNode` class and a function to insert values into a Binary Search Tree (BST). A BST is a data structure where each node has at most two children, referred to as the left child and the right ch...

The `insertIntoBST` function recursively inserts a new value into a BST. If the tree is empty, a new node is created. Otherwise, it compares the value to the current node's value: if smaller, it recurses on the left child; if larger, it recurses on the right child. Duplicate values are ignored in this implementation. The time complexity for insertion is O(h), where h is the height of the tree. In the best case (a balanced tree), h is log n, leading to O(log n) complexity. In the worst case (a skewed tree), h can be n, leading to O(n) complexity. The space complexity is O(h) due to the recursion stack. The `buildBSTFromArray` function demonstrates how to construct a BST by repeatedly calling `insertIntoBST` for each element in an array.

class TreeNode: value left_child = null right_child = null function insertIntoBST(root, value): if root is null: return new TreeNode(value) if value < root.value: root.left_child = insertIntoBST(root.left_child, value) e...

This PHP code defines a function to reverse a given string. It iterates through the string from the last character to the first, appending each character to a new string. This is a fundamental string manipulation task wi...

The `reverseString` function takes a string and returns its reversed version. It first checks for an empty string, returning an empty string if found. Otherwise, it initializes an empty string `$reversed`. A `for` loop iterates from the last index (`$length - 1`) down to 0. In each iteration, the character at the current index `$i` from the input string is appended to `$reversed`. The time complexity is O(n), where n is the length of the string, because each character is processed once. The space complexity is also O(n) due to the creation of the new reversed string. The `processStrings` helper function demonstrates how to apply this reversal to an array of strings.

function reverseString(input_string): if input_string is empty: return "" reversed_string = "" for i from length(input_string) - 1 down to 0: reversed_string = reversed_string + input_string[i] return reversed_string