This implementation performs a binary search on a sorted list of integers to find the index of a target value. Binary search is highly efficient for searching in large, ordered datasets, making it a fundamental algorithm...

The `binarySearch` function initiates a recursive search by calling `_binarySearchRecursive` with the initial search boundaries. The recursive helper function repeatedly divides the search interval in half. If the middle element matches the target, its index is returned. If the target is smaller, the search continues in the left sub-list; otherwise, it continues in the right sub-list. The recursion terminates when the target is found or when the search interval becomes empty (`low > high`), indicating the target is not present. The time complexity is O(log n) because the search space is halved in each step. The space complexity is O(log n) due to the recursion call stack. Edge cases include an empty list and the target being the first or last element.

FUNCTION binarySearch(sortedList, target): IF sortedList is empty THEN RETURN -1 END IF RETURN _binarySearchRecursive(sortedList, target, 0, length of sortedList - 1) END FUNCTION FUNCTION _binarySearchRecursive(sortedLi...

This function reverses a singly linked list in-place. Reversing a linked list is a common operation in data structure manipulation, often used in algorithms that require processing a list in reverse order or for implemen...

The `reverseLinkedList` function iterates through the linked list, reversing the direction of each node's `next` pointer. It uses three pointers: `prev` (initially null), `current` (initially the head), and `nextTemp` (to temporarily store the next node before `current.next` is modified). In each iteration, the `current` node's `next` pointer is set to `prev`, effectively reversing the link. Then, `prev` is updated to `current`, and `current` moves to the `nextTemp` node. The loop continues until `current` becomes null. The time complexity is O(n) because each node is visited exactly once. The space complexity is O(1) as the reversal is done in-place without using additional data structures proportional to the input size. Edge cases include an empty list and a list with only one node, both of which are handled by returning the original head.

CLASS ListNode: value next pointer END CLASS FUNCTION reverseLinkedList(head): prev = null current = head IF current is null OR current.next is null THEN RETURN head END IF WHILE current is not null: nextTemp = current.n...

This function finds the first character in a given string that does not repeat. It's useful for tasks like identifying unique identifiers or processing text where the first occurrence of a unique element is important. Fo...

The algorithm uses a hash map (Map in Dart) to store the frequency of each character in the input string. It iterates through the string once to populate the character counts. Then, it iterates through the string a second time, checking the count of each character in the map. The first character encountered with a count of 1 is returned. The time complexity is O(n) because we iterate through the string twice, where n is the length of the string. The space complexity is O(k), where k is the number of unique characters in the string, for storing the character counts. Edge cases include an empty string, for which an empty string is returned, and a string where all characters repeat, also returning an empty string.

FUNCTION findFirstNonRepeatingChar(string s): IF s is empty THEN RETURN "" END IF CREATE a map called charCounts FOR EACH character char in s: INCREMENT count for char in charCounts (initialize to 0 if not present) END F...

This function computes the factorial of a non-negative integer. The factorial of a number is the product of all positive integers less than or equal to that number. It's a fundamental concept in combinatorics and probabi...

The `calculateFactorial` function computes the factorial of `n` iteratively. It first handles invalid input (negative numbers) by throwing an `ArgumentError`. The base cases for `n = 0` and `n = 1` are handled by returning 1, as 0! and 1! are both defined as 1. For `n > 1`, a loop iterates from 2 up to `n`, multiplying the `result` by the current loop variable `i`. The time complexity is O(n) because the loop runs `n-1` times. The space complexity is O(1) as it uses a constant amount of extra space. Edge cases include negative input and the base cases of 0 and 1.

FUNCTION calculateFactorial(integer n): IF n < 0 THEN THROW error 'Factorial is not defined for negative numbers.' END IF IF n == 0 OR n == 1 THEN RETURN 1 END IF result = 1 FOR i FROM 2 TO n: result = result * i END FOR...

This Dart program reverses a given string. It utilizes a helper function to swap characters within a list representation of the string. This is a fundamental string manipulation technique with applications in data proces...

The `reverseString` function takes a string, converts it into a list of characters, and then uses a two-pointer approach to swap characters from the beginning and end until the pointers meet. The `swap` helper function facilitates the character exchange. The time complexity is O(n), where n is the length of the string, because each character is visited and swapped at most once. The space complexity is also O(n) due to the creation of the character list. Edge cases like empty strings and single-character strings are handled correctly, returning the string itself or an empty string respectively. The loop invariant is that the substring outside the pointers is always reversed.

function reverseString(str): if str is empty: return "" chars = split str into characters left = 0 right = length of chars - 1 while left < right: swap chars[left] and chars[right] increment left decrement right return j...

This Dart program implements the merge sort algorithm, a highly efficient, comparison-based sorting algorithm. It recursively divides the input list into smaller sublists, sorts them, and then merges the sorted sublists...

Merge sort operates on the divide and conquer principle. The `mergeSort` function recursively splits the list into halves until sublists of size 1 are obtained (which are inherently sorted). The `merge` helper function then combines these sorted sublists into a single sorted list. It uses temporary arrays `L` and `R` to hold the elements of the two sublists and merges them back into the original array `arr` in sorted order. The time complexity is O(n log n) in all cases (best, average, worst) because the list is always divided logarithmically, and merging takes linear time. The space complexity is O(n) due to the temporary arrays used during merging. Edge cases like empty lists and single-element lists are handled by the base case of the recursion (`left < right`).

function mergeSort(arr, left, right): if left < right: mid = left + (right - left) / 2 mergeSort(arr, left, mid) mergeSort(arr, mid + 1, right) merge(arr, left, mid, right) function merge(arr, left, mid, right): n1 = mid...

This Dart function performs a binary search on a sorted list of integers to find the index of a target value. Binary search is a highly efficient searching algorithm that works by repeatedly dividing the search interval...

The `binarySearch` function efficiently finds a target in a sorted list. It maintains a search interval defined by `low` and `high` pointers. In each iteration, it calculates the middle index and compares the element at `mid` with the target. If they match, the index is returned. If the middle element is less than the target, the search continues in the right half (`low = mid + 1`); otherwise, it searches the left half (`high = mid - 1`). The loop terminates when `low` exceeds `high`, indicating the target is not present. The time complexity is O(log n) due to halving the search space in each step, and space complexity is O(1). The loop invariant is that the target, if present, must lie within the `[low, high]` range.

function binarySearch(sortedList, target): low = 0 high = length of sortedList - 1 while low <= high: mid = low + (high - low) / 2 if sortedList[mid] == target: return mid else if sortedList[mid] < target: low = mid + 1...

This Dart program 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'. This is a classic example of recursio...

The `factorial` function calculates n! recursively. The base case is when n is 0, returning 1. For negative numbers, it throws an `ArgumentError` as factorial is undefined. The recursive step `n * factorial(n - 1)` breaks down the problem into smaller, identical subproblems. The time complexity is O(n) because the function calls itself n times. The space complexity is also O(n) due to the call stack depth. Correctness relies on the base case and the fact that each recursive call reduces n towards the base case. Handling negative input prevents infinite recursion.

function factorial(n): if n is 0: return 1 if n is less than 0: throw error "Factorial undefined for negative numbers" return n * factorial(n - 1)