This C code implements the binary search algorithm, a highly efficient method for finding an element within a sorted array. It works by repeatedly dividing the search interval in half. If the value of the search key is l...

The `binarySearch` function takes a sorted integer array, the lower and upper bounds of the search interval (`low` and `high`), and the `target` value to find. The `while (low <= high)` loop ensures the search continues as long as there's a valid interval. The `mid` index is calculated carefully as `low + (high - low) / 2` to prevent integer overflow that could occur with `(low + high) / 2` if `low` and `high` are very large. If `arr[mid]` matches the `target`, its index is returned. If `arr[mid]` is less than `target`, the search continues in the right half by setting `low = mid + 1`. Otherwise, it searches the left half by setting `high = mid - 1`. If the loop finishes without finding the target, -1 is returned. The time complexity is O(log n) because the search space is halved in each step. The space complexity is O(1) as it uses a constant amount of extra space. Edge cases include an empty array (where `high` will be -1 initially, making `low <= high` false), and the target being smaller than the smallest element or larger than the largest element.

function binarySearch(array, low, high, target): while low <= high: mid = low + (high - low) / 2 if array[mid] == target: return mid else if array[mid] < target: low = mid + 1 else: high = mid - 1 return -1 // Target not...

This program finds a peak element in an array. A peak element is defined as an element that is strictly greater than its adjacent neighbors. The function handles arrays of various sizes, including single-element arrays a...

The `findPeakElement` function iterates through the array to locate an element that is greater than both its left and right neighbors. It first checks the boundary conditions: if the array has only one element, that element is the peak. If the first element is greater than the second, it's a peak. Similarly, if the last element is greater than the second-to-last, it's a peak. For elements in the middle, it checks if `arr[i]` is greater than `arr[i-1]` and `arr[i+1]`. The time complexity is O(n) because in the worst case, we might iterate through the entire array. The space complexity is O(1) as we only use a few variables for storage. The correctness relies on the guarantee that at least one peak exists, ensuring the loop or boundary checks will eventually find one.

function findPeakElement(array, size): if size is 1: return array[0] if array[0] > array[1]: return array[0] if array[size-1] > array[size-2]: return array[size-1] for i from 1 to size-2: if array[i] > array[i-1] AND arr...

This C code implements a Trie (prefix tree) data structure. It allows for efficient insertion and searching of words. Each node in the Trie represents a character, and paths from the root to a node represent prefixes. A...

The Trie is a tree-like data structure where each node represents a character. The `createNode` function initializes a new node with its children pointers set to NULL and `isEndOfWord` to false. The `insert` function traverses the Trie, creating new nodes as needed for characters in the word, and marks the final node as `isEndOfWord = true`. The `search` function follows the path for the given word; if the path exists and the final node is marked as `isEndOfWord`, the word is found. The `freeTrie` function recursively deallocates memory to prevent leaks. The time complexity for both insert and search is O(L), where L is the length of the word, as we traverse at most L nodes. The space complexity depends on the number of nodes, which is related to the total number of characters in all inserted words and the branching factor (ALPHABET_SIZE). Edge cases include empty strings, words that are prefixes of other words, and invalid characters.

struct TrieNode: children[ALPHABET_SIZE] of TrieNode pointers isEndOfWord: boolean function createNode(): allocate memory for a new TrieNode initialize all children to NULL set isEndOfWord to false return the new node fu...

This C code implements a stack data structure using a singly linked list. A stack follows the Last-In, First-Out (LIFO) principle. The implementation includes functions for pushing elements onto the stack, popping elemen...

The stack is implemented using a linked list where each `Node` contains data and a pointer to the next node. The `Stack` structure itself holds a pointer to the `top` node and the current `size`. The `createNode` and `createStack` functions handle memory allocation for nodes and the stack structure, respectively, with error checking. The `push` operation creates a new node, sets its `next` pointer to the current `top`, and updates `stack->top` to the new node, incrementing the size. The `pop` operation checks for an empty stack (underflow), then removes the `top` node, frees its memory, updates `stack->top` to the next node, and decrements the size. The `peek` operation returns the data of the `top` node without removing it, also checking for an empty stack. `isEmpty` and `getSize` provide utility functions. The `freeStack` function iterates through the list, freeing each node and then the stack structure itself. The time complexity for `push`, `pop`, and `peek` is O(1) because these operations only involve manipulating the `top` of the stack. The space complexity is O(n), where n is the number of elements in the stack, due to the linked list nodes.

struct Node: data: integer next: pointer to Node struct Stack: top: pointer to Node size: integer function createNode(data): allocate memory for a new Node set node.data = data set node.next = NULL return node function c...

This C code implements a queue data structure using a singly linked list. A queue follows the First-In, First-Out (FIFO) principle. The implementation includes functions for adding elements to the rear (enqueue), removin...

The queue is implemented with a linked list where each `QNode` stores data and a pointer to the next node. The `Queue` structure maintains pointers to both the `front` and `rear` nodes, along with the `size`. `createQNode` and `createQueue` handle memory allocation and initialization. `enqueue` creates a new node and appends it to the `rear` of the queue. If the queue is empty, the new node becomes both `front` and `rear`. `dequeue` removes the node from the `front`, frees its memory, and updates `front`. It handles the special case where the queue becomes empty after dequeueing, setting both `front` and `rear` to `NULL`. `front` returns the data of the `front` node without removing it, checking for an empty queue. `isEmpty` and `getSize` are utility functions. `freeQueue` iterates through all nodes, freeing their memory, and then frees the queue structure. The time complexity for `enqueue`, `dequeue`, and `front` is O(1) because these operations only involve manipulating the `front` and `rear` pointers. The space complexity is O(n), where n is the number of elements in the queue, due to the linked list nodes.

struct QNode: data: integer next: pointer to QNode struct Queue: front: pointer to QNode rear: pointer to QNode size: integer function createQNode(data): allocate memory for a new QNode set node.data = data set node.next...

This C code implements an iterative function to reverse a singly linked list. It traverses the list, changing the `next` pointer of each node to point to its previous node. This is a fundamental operation for manipulatin...

The `reverseList` function reverses a singly linked list iteratively. It uses three pointers: `prev` (initially `NULL`), `current` (initially `head`), and `next_node` (to temporarily store the next node). In each iteration of the `while` loop, it first saves the `current->next` pointer into `next_node`. Then, it reverses the `current` node's `next` pointer to point to `prev`. Finally, it advances `prev` to `current` and `current` to `next_node`. This process continues until `current` becomes `NULL`, at which point `prev` points to the new head of the reversed list. Edge cases, such as an empty list (`head == NULL`) or a list with a single node (`head->next == NULL`), are handled by returning the `head` directly, as no reversal is needed. The time complexity is O(n) because each node is visited and processed once. The space complexity is O(1) as only a constant number of extra pointers are used.

function reverseList(head): prev = null current = head while current is not null: next_node = current.next current.next = prev prev = current current = next_node return prev

This C code implements Kadane's algorithm to find the maximum sum of a contiguous subarray within a given array of integers. It iterates through the array, maintaining a `current_max` sum and a `max_so_far` sum. This alg...

Kadane's algorithm efficiently solves the maximum subarray sum problem in linear time. The core idea is to iterate through the array, keeping track of the maximum sum ending at the current position (`current_max`) and the overall maximum sum found so far (`max_so_far`). If `current_max` becomes negative, it's reset to zero, as a negative sum would only decrease the potential maximum sum of any subsequent subarray. The algorithm handles arrays with all negative numbers by initializing `max_so_far` to the smallest possible integer, ensuring that the largest negative number is correctly identified as the maximum sum. The time complexity is O(n) because we traverse the array once. The space complexity is O(1) as we only use a few variables to store intermediate sums. The invariant maintained is that `max_so_far` always holds the maximum subarray sum found up to the current element.

function maxSubArraySum(array): if array is empty: return 0 max_so_far = negative infinity current_max = 0 for each element in array: current_max = current_max + element if current_max > max_so_far: max_so_far = current_...

This C code finds the index of the first non-repeating character in a given string. It uses a frequency array to count occurrences of each character and then iterates through the string again to find the first character...

The `firstUniqChar` function efficiently finds the index of the first non-repeating character in a string. It employs a two-pass approach. In the first pass, it iterates through the input string `s` and populates a frequency array `charCount` of size 26 (assuming lowercase English letters). Each index in `charCount` corresponds to a letter ('a' to 'z'), and its value stores the number of times that letter appears in the string. The second pass iterates through the string again. For each character, it checks its count in the `charCount` array. If the count is exactly 1, it means this is the first non-repeating character encountered, and its index `i` is returned. If the loop completes without finding any character with a count of 1, it signifies that all characters repeat or the string was empty, and -1 is returned. Edge cases like null or empty strings are handled at the beginning. The time complexity is O(n), where n is the length of the string, because we perform two linear passes. The space complexity is O(1) because the size of the frequency array is constant (26), regardless of the input string's length.

function firstUniqChar(string s): if s is null or empty: return -1 create frequency_map (array of size 26, initialized to 0) for each character c in s: increment count for c in frequency_map for each character c at index...