Divide and Conquer — (low+high)/2 Overflow Fix

package io.thecodeforge.algorithms;

public class SumOfArray {

    /**
     * Calculates the sum of all elements in an integer array
     * using the divide and conquer pattern.
     *
     * This is intentionally a simple example — summing an array
     * doesn't need D&C in practice (a plain loop is faster and clearer).
     * The point here is to see the three-step structure in its purest form
     * before we apply it to harder problems.
     *
     * @param numbers  the array to sum
     * @param left     the starting index of the current sub-array (inclusive)
     * @param right    the ending index of the current sub-array (inclusive)
     * @return         the total sum of elements from index left to right
     */
    public static int sumDivideAndConquer(int[] numbers, int left, int right) {

        // CONQUER — base case: a sub-array of exactly one element.
        // Its sum is itself. No further splitting needed.
        // This is the anchor that stops infinite recursion.
        if (left == right) {
            return numbers[left];
        }

        // DIVIDE — find the midpoint to split into two halves.
        // We use left + (right - left) / 2 instead of (left + right) / 2
        // to prevent integer overflow when indices are large.
        // This formula is equivalent mathematically but safe in 32-bit arithmetic.
        int midpoint = left + (right - left) / 2;

        // CONQUER — recursively sum the left half [left, midpoint]
        int leftSum  = sumDivideAndConquer(numbers, left, midpoint);

        // CONQUER — recursively sum the right half [midpoint+1, right]
        int rightSum = sumDivideAndConquer(numbers, midpoint + 1, right);

        // COMBINE — add both halves together.
        // This is the simplest possible combine step: just addition.
        // In merge sort this step is far more involved.
        return leftSum + rightSum;
    }

    public static void main(String[] args) {
        int[] salesFigures = {120, 340, 85, 210, 430, 95, 275};

        int totalSales = sumDivideAndConquer(salesFigures, 0, salesFigures.length - 1);

        System.out.println("Individual figures: ");
        for (int figure : salesFigures) {
            System.out.print(figure + " ");
        }
        System.out.println();
        System.out.println("Total sum (divide and conquer): " + totalSales);
        System.out.println("Verification (plain sum):       "
            + (120 + 340 + 85 + 210 + 430 + 95 + 275));
    }
}

package io.thecodeforge.algorithms;

public class RecursiveBinarySearch {

    /**
     * Searches for a target temperature in a sorted array of readings.
     * The array MUST be sorted in ascending order before calling this method.
     * Binary search on an unsorted array produces undefined results — no error,
     * just a confidently wrong answer. This is worth repeating.
     *
     * @param sortedTemps  a sorted array of integer temperature readings
     * @param left         the left boundary of the current search window (inclusive)
     * @param right        the right boundary of the current search window (inclusive)
     * @param target       the temperature value we are looking for
     * @return             the index of the target, or -1 if not present
     */
    public static int binarySearch(int[] sortedTemps, int left, int right, int target) {

        // CONQUER — base case: the search window has collapsed to nothing.
        // left > right means we have eliminated all candidates without finding the target.
        if (left > right) {
            return -1;
        }

        // DIVIDE — find the middle index of the current search window.
        // Always use left + (right - left) / 2, never (left + right) / 2.
        // See the production incident in this article for why this matters.
        int midIndex = left + (right - left) / 2;

        // CONQUER — direct hit: the target is at the midpoint.
        if (sortedTemps[midIndex] == target) {
            return midIndex;
        }

        // CONQUER + DIVIDE — target is smaller than midpoint value.
        // The target must be in the left half if it exists at all.
        // We discard the entire right half and recurse on [left, midIndex-1].
        if (sortedTemps[midIndex] > target) {
            return binarySearch(sortedTemps, left, midIndex - 1, target);
        }

        // CONQUER + DIVIDE — target is larger than midpoint value.
        // The target must be in the right half if it exists at all.
        // We discard the entire left half and recurse on [midIndex+1, right].
        return binarySearch(sortedTemps, midIndex + 1, right, target);

        // Note: there is no combine step here.
        // The answer comes from exactly one recursive call, not from merging two.
        // This is why binary search is described as 'decrease and conquer'.
    }

    public static void main(String[] args) {
        // Array must be sorted — binary search assumes this as a precondition.
        int[] dailyHighTemps = {-5, 2, 8, 14, 19, 23, 27, 31, 36};
        int targetTemp       = 23;
        int notPresentTemp   = 20;

        int foundIndex   = binarySearch(dailyHighTemps, 0, dailyHighTemps.length - 1, targetTemp);
        int missingIndex = binarySearch(dailyHighTemps, 0, dailyHighTemps.length - 1, notPresentTemp);

        System.out.println("Array: [-5, 2, 8, 14, 19, 23, 27, 31, 36]");
        System.out.println("Searching for " + targetTemp + "\u00b0C \u2192 found at index: " + foundIndex);
        System.out.println("Searching for " + notPresentTemp + "\u00b0C \u2192 result: " + missingIndex + " (not present)");

        // Demonstrate the logarithmic depth: log2(9) is approximately 3.17,
        // so at most 4 comparisons are needed for any search on this 9-element array.
        System.out.println("\nMax comparisons for 9 elements: ~"
            + (int) Math.ceil(Math.log(dailyHighTemps.length) / Math.log(2)));
        System.out.println("Max comparisons for 1,000,000 elements: ~"
            + (int) Math.ceil(Math.log(1_000_000) / Math.log(2)));
    }
}

package io.thecodeforge.algorithms;

import java.util.Arrays;

public class MergeSort {

    /**
     * Entry point for merge sort. Sorts the given integer array in ascending order.
     * This is a classic D&C implementation — clear structure over micro-optimisation.
     *
     * Time complexity:  O(n log n) — guaranteed, no bad cases unlike quicksort
     * Space complexity: O(n) — extra memory for the left and right sub-arrays
     * Stability:        Yes — equal elements preserve their original relative order
     *
     * @param items  the array of integers to sort, modified in place
     */
    public static void mergeSort(int[] items) {

        // BASE CASE — an array of 0 or 1 elements is already sorted by definition.
        // This is the anchor. Without it, the recursion never terminates.
        if (items.length <= 1) {
            return;
        }

        // DIVIDE — split into two roughly equal halves.
        // For an array of length 6: midpoint = 3, left = [0..2], right = [3..5].
        int midpoint = items.length / 2;

        // Arrays.copyOfRange creates a new array containing just the specified range.
        // This allocates O(n) extra memory — see the production insight below.
        int[] leftHalf  = Arrays.copyOfRange(items, 0, midpoint);
        int[] rightHalf = Arrays.copyOfRange(items, midpoint, items.length);

        // CONQUER — recursively sort each half independently.
        // These two calls are completely independent of each other.
        // That independence is what makes this D&C rather than DP.
        mergeSort(leftHalf);
        mergeSort(rightHalf);

        // COMBINE — merge the two now-sorted halves back into the original array.
        // All the sorting intelligence lives in merge(), not in the recursive calls above.
        merge(items, leftHalf, rightHalf);
    }

    /**
     * Merges two sorted arrays (leftHalf and rightHalf) into the destination array.
     * This is the heart of merge sort — study this method until you can write it
     * from memory, because interviewers will ask you to.
     *
     * The two-pointer technique: walk both input arrays simultaneously,
     * always writing the smaller of the two current front elements to the destination.
     * When one input is exhausted, copy whatever remains from the other.
     *
     * @param destination  the array to write merged results into
     * @param leftHalf     a fully sorted sub-array (left portion)
     * @param rightHalf    a fully sorted sub-array (right portion)
     */
    private static void merge(int[] destination, int[] leftHalf, int[] rightHalf) {
        int leftPointer  = 0; // current read position in leftHalf
        int rightPointer = 0; // current read position in rightHalf
        int destPointer  = 0; // current write position in destination

        // Main merge loop — runs until one of the two input arrays is exhausted.
        while (leftPointer < leftHalf.length && rightPointer < rightHalf.length) {

            // The <= here (rather than <) is what makes merge sort STABLE.
            // When elements are equal, we take from the left half first,
            // preserving the original relative order of equal elements.
            if (leftHalf[leftPointer] <= rightHalf[rightPointer]) {
                destination[destPointer] = leftHalf[leftPointer];
                leftPointer++;
            } else {
                destination[destPointer] = rightHalf[rightPointer];
                rightPointer++;
            }
            destPointer++;
        }

        // Drain remaining elements from leftHalf.
        // At most one of these two drain loops will execute — the other input
        // was already fully consumed in the main loop above.
        while (leftPointer < leftHalf.length) {
            destination[destPointer] = leftHalf[leftPointer];
            leftPointer++;
            destPointer++;
        }

        // Drain remaining elements from rightHalf.
        while (rightPointer < rightHalf.length) {
            destination[destPointer] = rightHalf[rightPointer];
            rightPointer++;
            destPointer++;
        }
    }

    public static void main(String[] args) {
        int[] examScores = {78, 45, 92, 13, 67, 55, 88, 23, 100, 34};

        System.out.println("Before sorting: " + Arrays.toString(examScores));
        mergeSort(examScores);
        System.out.println("After sorting:  " + Arrays.toString(examScores));

        // Merge sort handles already-sorted and reverse-sorted arrays
        // in the same O(n log n) time — no worst-case degradation unlike quicksort.
        int[] reverseOrdered = {9, 7, 5, 3, 1};
        System.out.println("\nReverse ordered before: " + Arrays.toString(reverseOrdered));
        mergeSort(reverseOrdered);
        System.out.println("Reverse ordered after:  " + Arrays.toString(reverseOrdered));

        int[] nearlyOrdered = {1, 2, 4, 3, 5, 6};
        System.out.println("\nNearly sorted before: " + Arrays.toString(nearlyOrdered));
        mergeSort(nearlyOrdered);
        System.out.println("Nearly sorted after:  " + Arrays.toString(nearlyOrdered));
    }
}

package io.thecodeforge.algorithms;

/**
 * Finds the contiguous sub-array with the maximum sum using divide and conquer.
 * This is a classic problem known as the Maximum Subarray Problem.
 *
 * Given an integer array (possibly with negative values), find the contiguous
 * sub-array that produces the largest sum.
 *
 * Example: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
 *          The maximum subarray is [4, -1, 2, 1] with sum = 6.
 *
 * Time complexity: O(n log n) — the D&C approach.
 * Note: Kadane's algorithm solves this in O(n) with a linear scan,
 * which is better in practice. This D&C version is presented because
 * it is a textbook example of the three-step pattern including a
 * non-trivial combine step, and it appears frequently in interviews.
 */
public class MaximumSubarraySum {

    public static int findMaxSubarraySum(int[] values, int left, int right) {

        // BASE CASE — a single element: the only possible subarray is itself.
        // Even if it is negative, it is the best (and only) option for this sub-problem.
        if (left == right) {
            return values[left];
        }

        // DIVIDE — find the midpoint and split into left and right halves.
        int midpoint = left + (right - left) / 2;

        // CONQUER — the maximum subarray in the full range is one of three things:
        // 1. Entirely within the left half
        int maxLeftSum  = findMaxSubarraySum(values, left, midpoint);

        // 2. Entirely within the right half
        int maxRightSum = findMaxSubarraySum(values, midpoint + 1, right);

        // 3. Crossing the midpoint — starts somewhere in the left half and
        //    ends somewhere in the right half
        // This third case is the key insight that makes D&C work here.
        // A crossing subarray cannot be found by either recursive call alone.
        int maxCrossingSum = findMaxCrossingSum(values, left, midpoint, right);

        // COMBINE — the answer for this range is the best of all three options.
        return Math.max(maxCrossingSum, Math.max(maxLeftSum, maxRightSum));
    }

    /**
     * Finds the maximum sum of any subarray that crosses the midpoint.
     * Such a subarray must include values[midpoint] and values[midpoint+1].
     * We extend as far left and as far right as the running sum allows.
     */
    private static int findMaxCrossingSum(int[] values, int left, int midpoint, int right) {

        // Extend leftward from the midpoint, accumulating the best possible left extension.
        // We scan right-to-left from midpoint to left.
        int leftRunningSum = Integer.MIN_VALUE;
        int runningTotal   = 0;
        for (int i = midpoint; i >= left; i--) {
            runningTotal  += values[i];
            if (runningTotal > leftRunningSum) {
                leftRunningSum = runningTotal;
            }
        }

        // Extend rightward from midpoint+1, accumulating the best possible right extension.
        int rightRunningSum = Integer.MIN_VALUE;
        runningTotal        = 0;
        for (int i = midpoint + 1; i <= right; i++) {
            runningTotal   += values[i];
            if (runningTotal > rightRunningSum) {
                rightRunningSum = runningTotal;
            }
        }

        // The crossing sum is the best left extension plus the best right extension.
        // Both halves must be included because the crossing subarray spans the midpoint.
        return leftRunningSum + rightRunningSum;
    }

    public static void main(String[] args) {
        int[] portfolioReturns = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

        int bestGain = findMaxSubarraySum(portfolioReturns, 0, portfolioReturns.length - 1);

        System.out.println("Daily returns: [-2, 1, -3, 4, -1, 2, 1, -5, 4]");
        System.out.println("Best consecutive gain window sum: " + bestGain);
        System.out.println("(Subarray [4, -1, 2, 1] gives sum = 6)");

        // The all-negative case is important: the algorithm should still return
        // the least-negative single element, not zero or Integer.MIN_VALUE.
        int[] allNegative = {-8, -3, -6, -2, -5};
        int leastBadLoss  = findMaxSubarraySum(allNegative, 0, allNegative.length - 1);
        System.out.println("\nAll-negative returns: [-8, -3, -6, -2, -5]");
        System.out.println("Best (least bad) element: " + leastBadLoss);
        System.out.println("(Correctly returns -2, not 0 or Integer.MIN_VALUE)");
    }
}

// io.thecodeforge — dsa tutorial

public class InPlaceMergeSort {

    // Production version — O(1) extra space, O(n log n) time
    public static void sort(int[] data) {
        if (data.length < 2) return;
        sortRange(data, 0, data.length);
    }

    private static void sortRange(int[] data, int start, int end) {
        if (end - start < 2) return;
        int mid = (start + end) >>> 1;
        sortRange(data, start, mid);
        sortRange(data, mid, end);
        mergeInPlace(data, start, mid, end);
    }

    private static void mergeInPlace(int[] data, int start, int mid, int end) {
        int left = start;
        int right = mid;
        while (left < right && right < end) {
            if (data[left] <= data[right]) {
                left++;
            } else {
                // Rotate the element at 'right' into its correct position
                int value = data[right];
                System.arraycopy(data, left, data, left + 1, right - left);
                data[left] = value;
                left++;
                right++;
                mid++; // mid moves right because we inserted
            }
        }
    }

    public static void main(String[] args) {
        int[] data = {38, 27, 43, 3, 9, 82, 10};
        sort(data);
        for (int v : data) System.out.print(v + " ");
    }
}

// io.thecodeforge — dsa tutorial

import java.util.concurrent.RecursiveAction;
import java.util.concurrent.ForkJoinPool;

public class ParallelQuickSort extends RecursiveAction {

    private static final int THRESHOLD = 10_000; // tuned for this workload
    private final int[] data;
    private final int left;
    private final int right;

    public ParallelQuickSort(int[] data, int left, int right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    @Override
    protected void compute() {
        if (right - left < THRESHOLD) {
            // Sequential quicksort for small ranges
            java.util.Arrays.sort(data, left, right + 1);
            return;
        }
        int pivotIndex = partition(data, left, right);
        // Fork — schedule subtasks in parallel
        invokeAll(
            new ParallelQuickSort(data, left, pivotIndex - 1),
            new ParallelQuickSort(data, pivotIndex + 1, right)
        );
    }

    private int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
            }
        }
        int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp;
        return i + 1;
    }

    public static void main(String[] args) {
        int[] data = {38, 27, 43, 3, 9, 82, 10, 1, 22, 5};
        ForkJoinPool pool = new ForkJoinPool();
        pool.invoke(new ParallelQuickSort(data, 0, data.length - 1));
        for (int v : data) System.out.print(v + " ");
    }
}

// io.thecodeforge — dsa tutorial

public class DivideStep {
    // Binary search — O(1) divide, O(log n) total
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;  // O(1) divide
            if (arr[mid] == target) return mid;
            if (arr[mid] < target) left = mid + 1; // discard left half
            else right = mid - 1;                  // discard right half
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] data = {2, 5, 8, 12, 16, 23, 38, 45};
        System.out.println(binarySearch(data, 23));
        System.out.println(binarySearch(data, 1));
    }
}

// io.thecodeforge — dsa tutorial

public class MergeCombine {
    // In-place merge using pre-allocated buffer (memory-efficient)
    public static void merge(int[] arr, int l, int m, int r, int[] buf) {
        System.arraycopy(arr, l, buf, l, r - l + 1);
        int i = l, j = m + 1, k = l;
        while (i <= m && j <= r) {
            arr[k++] = (buf[i] <= buf[j]) ? buf[i++] : buf[j++];
        }
        while (i <= m) arr[k++] = buf[i++];
        // j > r — remaining elements already in place
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        int[] buf = new int[arr.length];
        // Simulate one merge step: [38,27,43,3] and [9,82,10] sorted halves
        int[] leftSorted = {3, 27, 38, 43};  // sorted first half
        int[] rightSorted = {9, 10, 82};     // sorted second half
        // Copy into arr for demo
        System.arraycopy(leftSorted, 0, arr, 0, 4);
        System.arraycopy(rightSorted, 0, arr, 4, 3);
        merge(arr, 0, 3, 6, buf);
        for (int v : arr) System.out.print(v + " ");
    }
}

// io.thecodeforge — dsa tutorial

public class BinarySearch {
    public static int search(int[] arr, int target, int lo, int hi) {
        if (lo > hi) return -1;                // base: not found
        if (lo == hi)                           // base: single element
            return arr[lo] == target ? lo : -1;
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target)
            return search(arr, target, mid + 1, hi);
        else
            return search(arr, target, lo, mid - 1);
    }
}

// io.thecodeforge — dsa tutorial

import java.util.*;

public class CountSmaller {
    public List<Integer> countSmaller(int[] nums) {
        Integer[] res = new Integer[nums.length];
        TreeMap<Integer, Integer> tree = new TreeMap<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            res[i] = tree.headMap(nums[i], false).values()
                           .stream().mapToInt(Integer::intValue).sum();
            tree.merge(nums[i], 1, Integer::sum);
        }
        return Arrays.asList(res);
    }
}