This program solves the Word Break II problem, which involves segmenting a given string into a space-separated sequence of one or more dictionary words. It returns all possible valid segmentations. This problem is a clas...

The `wordBreak` method uses a recursive backtracking approach with memoization to find all possible ways to segment a string `s` into words from a given dictionary `wordDict`. The `backtrack` helper function explores all possible splits. For each substring starting at `start`, it checks if it's a valid word. If it is, it recursively calls itself for the remainder of the string. The results from the recursive calls are combined with the current word. Memoization (`memo` map) is crucial to store the results for substrings that have already been processed, preventing redundant computations and significantly improving performance. The time complexity, with memoization, is roughly O(n^3) in the worst case (where n is the length of the string), due to substring operations and the number of possible segmentations. The space complexity is O(n^2) in the worst case for storing results in the memoization map and the recursion stack. Edge cases include an empty input string or an empty dictionary, which are handled. The correctness relies on the exhaustive exploration of all valid word combinations and the guarantee that if a substring can be segmented, all its valid segmentations will be found and combined.

function wordBreak(s, wordDict): memo = empty map dict = convert wordDict to a set return backtrack(s, dict, 0, memo) function backtrack(s, dict, start, memo): if start is in memo: return memo[start] results = empty list...

This program finds a peak element in an array. A peak element is an element that is strictly greater than its neighbors. The algorithm assumes that nums[-1] = nums[n] = -infinity, which simplifies boundary checks. This i...

The `findPeakElement` method utilizes a binary search approach to efficiently locate a peak element. The core idea is that if `nums[mid] < nums[mid + 1]`, then a peak must exist to the right of `mid` (including `mid + 1`), so we move `left = mid + 1`. Conversely, if `nums[mid] > nums[mid + 1]`, a peak must exist at or to the left of `mid`, so we set `right = mid`. This process continues until `left` equals `right`, at which point `left` (or `right`) is guaranteed to be an index of a peak element. The time complexity is O(log n) due to the binary search. The space complexity is O(1) as it uses a constant amount of extra space. Edge cases like an empty or null array are handled by throwing an exception. The invariant maintained is that a peak element always exists within the range `[left, right]`.

function findPeakElement(nums): if nums is null or empty: throw error return findPeak(nums, 0, length(nums) - 1) function findPeak(nums, left, right): while left < right: mid = left + (right - left) / 2 if nums[mid] > nu...

This program implements the classic Two Sum problem. Given an array of integers `nums` and an integer `target`, it finds two numbers in the array such that they add up to `target`. The function returns the indices of the...

The `twoSum` method efficiently solves the Two Sum problem using a hash map, achieving an average time complexity of O(n). It iterates through the array once. For each element `nums[i]`, it calculates the `complement` needed to reach the `target` (`complement = target - nums[i]`). It then checks if this `complement` already exists as a key in the `numMap`. If it does, it means we've found the pair, and we return the index of the complement (stored in the map) and the current index `i`. If the `complement` is not found, the current number `nums[i]` and its index `i` are added to the `numMap` for future lookups. This approach ensures that each number is processed at most once. The space complexity is O(n) in the worst case, as the hash map might store all elements of the array. Edge cases handled include null or arrays with fewer than two elements, and the case where no solution exists (though the problem statement often guarantees one solution). The invariant is that at any point, `numMap` contains all numbers encountered so far and their indices, and if a solution exists, it will be found when its second element is processed.

function twoSum(nums, target): if nums is null or length(nums) < 2: throw error numMap = empty hash map for i from 0 to length(nums) - 1: complement = target - nums[i] if complement is in numMap: return [numMap[complemen...

This program calculates the length of the Longest Increasing Subsequence (LIS) within a given array of integers. An increasing subsequence is a sequence of elements from the original array that are in increasing order, a...

The `lengthOfLIS` method computes the length of the Longest Increasing Subsequence using an optimized dynamic programming approach with binary search, achieving O(n log n) time complexity. It maintains an array `dp` where `dp[i]` stores the smallest ending element of all increasing subsequences of length `i+1`. For each number `num` in the input array, we perform a binary search on `dp` to find the smallest element that is greater than or equal to `num`. If `num` is greater than all elements in `dp` up to the current `length`, it means we can extend the LIS, and `length` is incremented. Otherwise, `num` replaces the found element in `dp`, potentially allowing for a longer LIS later by having a smaller tail element for a subsequence of that length. The space complexity is O(n) for the `dp` array. Edge cases include empty or null input arrays, which correctly return 0. The invariant is that `dp` always stores the smallest tail elements for increasing subsequences of lengths 1 to `length` in sorted order.

function lengthOfLIS(nums): if nums is null or empty: return 0 dp = array of size nums.length, initialized to 0 length = 0 for each num in nums: low = 0, high = length while low < high: mid = low + (high - low) / 2 if dp...

This Java code implements a Queue data structure using a fixed-size array, employing a circular buffer approach. It allows for efficient addition (enqueue) and removal (dequeue) of elements, managing the array indices to...

The `ArrayQueue` implementation has a time complexity of O(1) for enqueue, dequeue, peek, isEmpty, isFull, and size operations, assuming the array operations are O(1). This is because each operation involves a constant number of steps, regardless of the number of elements in the queue. The space complexity is O(n), where n is the maximum capacity of the queue, as it uses an array of fixed size to store the elements. Edge cases handled include a full queue (preventing enqueue) and an empty queue (preventing dequeue/peek), both of which throw `IllegalStateException`. The circular buffer logic is managed by the `front` and `rear` pointers and the modulo operator (`% maxSize`), which ensures that indices wrap around correctly. `currentSize` is used to track the number of elements, distinguishing between a full and empty queue when `front` and `rear` might otherwise be equal.

class ArrayQueue(capacity): array = new array of size capacity maxSize = capacity front = 0 rear = -1 currentSize = 0 function enqueue(item): if isFull(): throw error "Queue is full" rear = (rear + 1) % maxSize array[rea...

This Java code provides an in-place algorithm to reverse an array. It uses two pointers, one starting at the beginning and the other at the end of the array, and swaps elements until the pointers meet or cross. This is a...

The in-place array reversal algorithm has a time complexity of 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) as it only uses a constant amount of extra space for temporary variables (like `temp`, `left`, `right`). Edge cases handled include null arrays, empty arrays, and arrays with a single element, for which no reversal is performed. The loop invariant is that the elements from index 0 up to `left-1` and from `right+1` up to `arr.length-1` are in their final reversed positions. The algorithm works by iteratively swapping the element at the `left` pointer with the element at the `right` pointer, then moving `left` one step forward and `right` one step backward. This continues until `left` is no longer less than `right`, ensuring the entire array is reversed.

function reverseArrayInPlace(array): if array is null or array.length <= 1: return left = 0 right = array.length - 1 while left < right: swap array[left] and array[right] increment left decrement right

This Java code implements the Merge Sort algorithm, a highly efficient, comparison-based sorting technique. It works by recursively dividing the input array into smaller sub-arrays, sorting them, and then merging the sor...

Merge Sort has a time complexity of O(n log n) in all cases (best, average, and worst), making it a very reliable sorting algorithm. Its space complexity is O(n) due to the auxiliary space required for the temporary arrays during the merge step. Edge cases handled include null arrays, empty arrays, and arrays with a single element, which are returned as is. The algorithm's correctness relies on the divide-and-conquer strategy: the base case is an array of size 0 or 1, which is considered sorted. For larger arrays, it's split into two halves, each sorted recursively. The crucial part is the `merge` function, which takes two already sorted sub-arrays and combines them into a single sorted array by comparing elements from both sub-arrays and placing the smaller one into the correct position in the main array. This process ensures that the entire array is sorted upon completion of the recursive calls.

function mergeSort(array): if array is null or length <= 1: return mergeSortHelper(array, 0, array.length - 1) function mergeSortHelper(array, left, right): if left < right: mid = left + (right - left) / 2 mergeSortHelpe...

This Java code implements the binary search algorithm. It efficiently finds the index of a target value within a sorted array by repeatedly dividing the search interval in half. This is commonly used in applications wher...

The binary search algorithm has a time complexity of O(log n), where n is the number of elements in the array. This is because the search space is halved in each step. The space complexity is O(1) as it uses a constant amount of extra space for variables. Edge cases handled include null or empty arrays, where it correctly returns -1. The loop invariant is that the target element, if present, is always within the range [low, high]. The algorithm works by comparing the target with the middle element; if they match, the index is returned. If the target is greater, the search continues in the right half (low becomes mid + 1). If the target is smaller, the search continues in the left half (high becomes mid - 1). This process continues until the target is found or the search space is exhausted (low > high).

function binarySearch(array, target): if array is null or empty: return -1 low = 0 high = array.length - 1 while low <= high: mid = low + (high - low) / 2 if array[mid] == target: return mid else if array[mid] < target:...