This algorithm finds the minimum element in a rotated sorted array, which is an array that was originally sorted in ascending order and then rotated at some pivot point. The array might contain duplicate elements. It emp...

The `FindMin` function uses a binary search approach adapted for rotated sorted arrays, specifically handling duplicates. The core idea is to compare the middle element (`nums(mid)`) with the rightmost element (`nums(right)`). If `nums(mid) > nums(right)`, it implies that the rotation point (and thus the minimum element) lies in the right half of the array (`[mid + 1, right]`). If `nums(mid) < nums(right)`, the minimum element must be in the left half, including `mid` (`[left, mid]`). The most challenging scenario arises when `nums(mid) == nums(right)`. In this case, we cannot definitively determine which half contains the minimum. To resolve this, we safely discard the rightmost element by decrementing `right`. This is because if `nums(right)` is the minimum, `nums(mid)` is also a candidate, and we will eventually find it. If `nums(right)` is not the minimum, discarding it does not lose the true minimum. The loop invariant is that the minimum element is always contained within the `[left, right]` range. The time complexity is O(log n) on average, but degrades to O(n) in the worst case where all elements are identical due to the duplicate handling. The space complexity is O(1) as it uses a constant amount of extra space.

Function FindMin(array): If array is empty, throw error. Set left = 0, right = length of array - 1. While left < right: Calculate mid = left + (right - left) / 2. If array[mid] > array[right]: Set left = mid + 1. Else If...

This function computes the sum of all digits in a given non-negative integer. For example, the sum of digits for 123 is 1 + 2 + 3 = 6. This is a fundamental operation used in various number theory problems, checksum calc...

The `SumOfDigits` function iteratively extracts the last digit of a number and adds it to a running sum. The modulo operator (`Mod 10`) retrieves the last digit, and integer division (`\\ 10`) effectively removes it. This process continues until the number becomes zero. The loop invariant is that `sum` holds the sum of digits processed so far, and `currentNumber` holds the remaining part of the original number. The time complexity is O(d), where d is the number of digits in the input integer, which is logarithmic with respect to the value of the integer (O(log n)). The space complexity is O(1) as it uses a fixed amount of extra memory. The function correctly handles the edge case of `n = 0` as the `While` loop condition `currentNumber > 0` will be false, and it will return the initialized `sum` of 0.

Function SumOfDigits(number): If number is negative, throw error. Initialize sum = 0. While number > 0: digit = number modulo 10. Add digit to sum. Divide number by 10 (integer division). Return sum.

This function reverses the elements of an array in-place, meaning it modifies the original array directly without allocating any additional memory for a new array. It achieves this by swapping elements from the beginning...

The `ReverseArrayInPlace` function utilizes two pointers, `left` starting at the beginning of the array and `right` starting at the end. The algorithm iteratively swaps the elements pointed to by `left` and `right` and then moves `left` one step forward and `right` one step backward. The loop continues as long as `left` is less than `right`. The loop invariant is that all elements outside the range `[left, right]` have already been swapped into their final reversed positions. The time complexity is O(n), where n is the number of elements in the array, because each element is swapped at most once. The space complexity is O(1) because the reversal is performed in-place, using only a constant amount of extra space for the temporary variable used during swapping. Edge cases such as null arrays, empty arrays, and arrays with a single element are handled by the initial conditional check, preventing any operations on invalid inputs and ensuring correctness.

Function ReverseArrayInPlace(array): If array is null or has 0 or 1 element, return. Initialize left pointer to 0. Initialize right pointer to length of array - 1. While left < right: Swap element at left with element at...

This algorithm finds a peak element in an array where a peak is defined as an element strictly greater than its neighbors. It uses a binary search approach to efficiently locate such an element. This is useful in scenari...

The `FindPeakElement` function implements a modified binary search to locate a peak element in an array. A peak element is guaranteed to exist because we can imagine that `nums[-1] = nums[n] = -infinity`. The algorithm iteratively narrows down the search space. If `nums[mid] < nums[mid + 1]`, it implies that a peak must exist to the right of `mid` (inclusive of `mid + 1`), so `left` is updated to `mid + 1`. Otherwise, if `nums[mid] >= nums[mid + 1]`, a peak must exist at `mid` or to its left, so `right` is updated to `mid`. The loop invariant is that a peak element is always present within the `[left, right]` range. The time complexity is O(log n) due to the binary search, and the space complexity is O(1) as it uses a constant amount of extra space. Edge cases like empty or single-element arrays are handled implicitly by the binary search logic and explicitly by an initial check.

Function FindPeakElement(array): If array is empty, throw error. Set left = 0, right = length of array - 1. While left < right: Calculate mid = left + (right - left) / 2. If array[mid] < array[mid + 1]: Set left = mid +...

This algorithm finds a peak element in an array where a peak is defined as an element strictly greater than its neighbors. The problem statement often assumes that the elements at indices -1 and n (where n is the array l...

The `FindPeakElement` function utilizes a binary search approach to efficiently locate a peak element. 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 for indices and does not require additional data structures. Edge cases such as empty or single-element arrays are handled. The algorithm also explicitly checks the boundaries of the array to see if the first or last elements are peaks. The core logic relies on the observation that if an element is not a peak, then at least one of its neighbors must be greater. By moving towards the greater neighbor, we are guaranteed to eventually find a peak. The invariant maintained is that a peak element must exist within the current search range [left, right].

function findPeakElement(nums): if nums is empty or null: throw error n = length of nums if n == 1: return 0 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: m...

This function computes the sum of the digits of a given non-negative integer. It iteratively extracts the last digit of the number using the modulo operator and adds it to a running sum. The number is then divided by 10...

The `SumOfDigits` function has a time complexity of O(log10 n), where n is the input number, because the number of iterations is proportional to the number of digits in n. The space complexity is O(1) as it only uses a constant amount of extra space for variables. The edge case of an input of 0 is handled correctly, returning 0. The loop invariant is that `sum` always holds the sum of digits of the original number that have already been processed, and `n` holds the remaining part of the number. The loop terminates when `n` becomes 0, at which point `sum` contains the total sum of all digits.

function sumOfDigits(n): sum = 0 if n == 0: return 0 while n > 0: digit = n modulo 10 sum = sum + digit n = n integer divide 10 return sum

This procedure reverses a character array (representing a string) in-place. It uses two pointers, one starting at the beginning of the array and the other at the end. Characters pointed to by these pointers are swapped,...

The `ReverseStringInPlace` procedure has a time complexity of O(n/2), which simplifies to O(n), where n is the length of the character array. This is because each character is swapped at most once. The space complexity is O(1) because the reversal is done in-place, using only a constant amount of extra space for the temporary variable used during swapping. Edge cases like null, empty, or single-character arrays are handled by returning immediately. The loop invariant is that the portion of the array from index 0 to `left - 1` and from `right + 1` to `s.Length - 1` is correctly reversed. The loop terminates when `left >= right`, at which point the entire array is reversed.

procedure reverseStringInPlace(s): if s is null or length of s <= 1: return left = 0 right = length of s - 1 while left < right: temp = s[left] s[left] = s[right] s[right] = temp left = left + 1 right = right - 1

This function determines if any permutation of a given string can form a palindrome. It works by counting the occurrences of each alphanumeric character, ignoring case and non-alphanumeric characters. A string can be rea...

The `CanPermutePalindrome` function has a time complexity of O(n), where n is the length of the input string, because it iterates through the string once to count characters and then iterates through the dictionary (at most 26 entries for English alphabet + 10 digits). The space complexity is O(k), where k is the number of unique alphanumeric characters in the string (at most 36 for English alphabet and digits), due to the dictionary storage. The algorithm correctly handles edge cases like null, empty, or whitespace strings. The core logic relies on the property that a palindrome can have at most one character with an odd frequency. The `CanPermutePalindromeBitVector` helper demonstrates an alternative O(1) space approach for ASCII characters by using a bit vector to track parity.

function canPermutePalindrome(str): if str is null or whitespace: return true charCounts = new dictionary for each char c in str: if c is letter or digit: lowerChar = toLower(c) if lowerChar is in charCounts: charCounts[...