This KQL query implements a function to find the median of two sorted arrays. It employs a binary search approach on the smaller array to efficiently find the correct partition points. The goal is to divide both arrays s...

The `findMedianSortedArrays` function aims to find the median of two sorted arrays `nums1` and `nums2` in O(log(min(m, n))) time complexity, where m and n are the lengths of the arrays. It first ensures that `nums1` is the shorter array to optimize the binary search. The core idea is to perform a binary search on `nums1` to find a partition point (`partitionX`) such that when combined with a corresponding partition point in `nums2` (`partitionY`), the elements are correctly divided. Specifically, we need `maxX <= minY` and `maxY <= minX`, where `maxX` and `maxY` are the largest elements in the left partitions, and `minX` and `minY` are the smallest elements in the right partitions. If the total length is odd, the median is the maximum of `maxX` and `maxY`. If the total length is even, the median is the average of `max(maxX, maxY)` and `min(minX, minY)`. Edge cases like empty arrays or one array being significantly larger are handled by the partition logic and the use of `real.Max` and `-real.Max` to represent boundary conditions.

FUNCTION findMedianSortedArrays(nums1, nums2): m = length(nums1) n = length(nums2) IF m > n THEN SWAP nums1 and nums2, m and n totalLength = m + n halfLen = floor((totalLength + 1) / 2) low = 0 high = m WHILE low <= high...

This KQL query defines a function to find the index of the first character that appears only once in a given string. It iterates through the string, counts the occurrences of each character using a temporary table, and t...

The `findFirstNonRepeatingChar` function first handles the edge case of an empty input string by returning -1. It then iterates through the string to build a frequency count of each character. A temporary table `charCounts` stores each character and its corresponding count. After counting, it iterates through the string a second time. For each character, it checks its count in `charCounts`. If the count is 1, the index of that character is returned. If the loop completes without finding such a character, it means all characters repeat, and -1 is returned. The time complexity is O(N) because we iterate through the string twice, and table operations are generally efficient for small alphabets. The space complexity is O(K) where K is the number of unique characters in the string, for storing character counts.

FUNCTION findFirstNonRepeatingChar(inputString): IF inputString is empty THEN RETURN -1 INITIALIZE empty charCounts table INITIALIZE empty processedChars string FOR i FROM 0 TO length(inputString) - 1: currentChar = char...

This KQL implementation demonstrates a Trie (prefix tree) data structure, commonly used for efficient string searching and autocomplete functionalities. It allows for rapid retrieval of all words that share a common pref...

The Trie implementation consists of nodes, where each node represents a character in a string. Each node has a flag indicating if it marks the end of a word and a collection of child nodes, keyed by the next character. The `insertWord` function traverses the Trie, creating new nodes as needed for each character in the word. If a node already exists for a character, it's reused. The `searchPrefix` function navigates to the node corresponding to the end of the given prefix. From that node, a recursive helper function `collectWords` explores all descendant paths to gather all complete words that start with that prefix. The time complexity for insertion is O(L), where L is the length of the word. Prefix search is also O(P + N), where P is the length of the prefix and N is the number of words found. Space complexity is O(T), where T is the total number of characters in all inserted words. Edge cases include empty strings, prefixes not found, and words that are prefixes of other words.

TrieNode: isEndOfWord: boolean children: map (char -> TrieNode) function insertWord(root, word): currentNode = root for each char in word: if char not in currentNode.children: create new TrieNode currentNode.children[cha...

This KQL function determines the longest common prefix (LCP) among an array of strings. The LCP is the longest string that is a prefix of all strings in the array. This is a common string manipulation task used in variou...

The `findLongestCommonPrefix` function takes a dynamic array of strings. It first handles the edge case of an empty input array by returning an empty string. It then uses the first string in the array as a reference and initializes `prefixLength` to its length. The function iterates through the remaining strings in the array. For each string, it compares characters with the reference string character by character, up to the current `prefixLength` and the length of the current string. It updates `currentPrefixLength` for each matching character. If a mismatch occurs, the inner loop breaks. The overall `prefixLength` is then updated to the minimum of its current value and `currentPrefixLength`. If `prefixLength` ever becomes 0, it means there's no common prefix, and an empty string is returned immediately. Finally, it returns the substring of the first string from index 0 up to the final `prefixLength`. The time complexity is O(S * L), where S is the number of strings and L is the length of the shortest string (in the worst case, all strings are identical and long). Space complexity is O(1) as it only uses a few variables.

function findLongestCommonPrefix(strs): if strs is empty: return "" firstStr = strs[0] prefixLength = length of firstStr for i from 1 to length of strs - 1: currentStr = strs[i] currentPrefixLength = 0 for j from 0 to mi...

This KQL function identifies the first character that repeats within an input string. It's useful for tasks like data validation, where you might need to detect duplicate entries or patterns in textual data. For example,...

The function `findFirstRecurringChar` takes a string and returns the first character that occurs more than once. It first splits the string into individual characters and counts their occurrences using `bag_pack_array` and `summarize count()`. Then, it filters these counts to identify characters that appear more than once. The function iterates through these recurring characters, finding the index of their first appearance in the original string. It keeps track of the character with the smallest index, which corresponds to the first recurring character. Edge cases like an empty input string or a string with no recurring characters are handled by returning an empty string. The time complexity is roughly O(N*M) where N is the length of the string and M is the number of unique characters, due to repeated string searches. Space complexity is O(M) for storing character counts.

function findFirstRecurringChar(inputString): if inputString is empty: return "" create a map to store character counts for each character in inputString: increment count for character in map create a list of recurring c...

This KQL function reverses a given string. It iterates through the input string from the last character to the first, appending each character to a new string. This is a fundamental string manipulation technique with app...

The `reverseString` function takes a string `inputString` and returns its reversed version. It initializes an empty string `reversed`. It then gets the length of the input string. If the string is empty, it returns an empty string immediately. Otherwise, it iterates from the last character of the input string (index `len - 1`) down to the first character (index 0). In each iteration, it takes the character at the current index `i` using `substring` and appends it to the `reversed` string using `strcat`. After the loop completes, the `reversed` string holds the reversed version of the original string, which is then returned. The time complexity is O(N), where N is the length of the string, because each character is processed once for appending. The space complexity is O(N) to store the new reversed string.

function reverseString(inputString): reversed = "" len = length of inputString if len == 0: return "" for i from len - 1 down to 0: reversed = reversed + inputString[i] return reversed

This KQL implementation demonstrates Depth First Search (DFS) for graph traversal. DFS explores as far as possible along each branch before backtracking. It's fundamental for solving problems like finding connected compo...

The `dfs` function performs a Depth First Search on a graph represented by an adjacency list. It takes the graph, a starting node, and a set of visited nodes (initially empty) as input. The function first marks the current `startNode` as visited and prints it. It then retrieves the neighbors of the `startNode` from the adjacency list. For each neighbor, it checks if it has already been visited. If not, it recursively calls `dfs` on that neighbor, passing the updated `visited` set. This recursive process ensures that the algorithm explores deeply into each branch before moving to the next. The use of the `visited` set is crucial to prevent infinite loops in graphs with cycles. The time complexity of DFS is O(V + E), where V is the number of vertices and E is the number of edges, as each vertex and edge is visited at most once. The space complexity is O(V) in the worst case for the recursion stack and the visited set.

function dfs(graph, currentNode, visited): add currentNode to visited print currentNode for each neighbor in graph[currentNode]: if neighbor is not in visited: dfs(graph, neighbor, visited) // Initialization: // visited...

This KQL function finds a single missing number in a sequence of distinct numbers ranging from 0 to N. It leverages the mathematical property that the sum of numbers from 0 to N can be easily calculated. By comparing thi...

The `findMissingNumber` function takes a dynamic array `numbers` which is assumed to contain distinct numbers from 0 to N, with exactly one number missing. It first determines `n`, the expected upper bound of the sequence (which is the length of the input array). It then calculates the `expectedSum` of numbers from 0 to `n` using the formula `n * (n + 1) / 2`. Next, it iterates through the input array to calculate the `actualSum` of its elements. The missing number is simply the difference between `expectedSum` and `actualSum`. An edge case for an empty array is handled by returning 0, assuming the sequence was meant to be just `[0]`. The time complexity is O(N) because it iterates through the array once to calculate the sum. The space complexity is O(1) as it only uses a few variables for calculations.

function findMissingNumber(numbers): n = length of numbers if n is 0: return 0 expectedSum = n * (n + 1) / 2 actualSum = 0 for each number in numbers: actualSum = actualSum + number return expectedSum - actualSum