Sliding Window — LinkedList Race Condition in Averages

package io.thecodeforge.algorithms;

public class MaxSumFixedWindow {

    /**
     * Finds the maximum sum of any contiguous subarray of exactly 'windowSize' elements.
     * Time:  O(n)  — each element is added once and removed once
     * Space: O(1)  — no extra data structures needed
     */
    public static int findMaxSum(int[] prices, int windowSize) {
        int totalElements = prices.length;

        // Edge case: window is larger than the array itself
        if (windowSize > totalElements) {
            throw new IllegalArgumentException(
                "Window size " + windowSize + " exceeds array length " + totalElements
            );
        }

        // Step 1: Build the first window by summing the first 'windowSize' elements
        int currentWindowSum = 0;
        for (int i = 0; i < windowSize; i++) {
            currentWindowSum += prices[i];
        }

        // The first window is our baseline best answer
        int maxSum = currentWindowSum;

        // Step 2: Slide the window one position at a time across the rest of the array
        for (int rightEdge = windowSize; rightEdge < totalElements; rightEdge++) {
            int leftEdge = rightEdge - windowSize; // the element we're dropping off the left

            // Drop the outgoing element, add the incoming element — one operation each
            currentWindowSum += prices[rightEdge];   // new element entering from the right
            currentWindowSum -= prices[leftEdge];    // old element leaving from the left

            // Update our best answer if this window beats it
            maxSum = Math.max(maxSum, currentWindowSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] dailyStockPrices = {12, 5, 35, 8, 6, 14, 21, 9, 3, 18, 27, 11, 4, 16};
        int targetWindowDays = 4;

        int result = findMaxSum(dailyStockPrices, targetWindowDays);
        System.out.println("Stock prices: " + java.util.Arrays.toString(dailyStockPrices));
        System.out.println("Max 4-day sum: " + result);
    }
}

package io.thecodeforge.algorithms;

import java.util.HashMap;
import java.util.Map;

public class LongestSubstringKDistinct {

    /**
     * Finds the length of the longest substring with at most 'maxDistinct' distinct characters.
     * Time:  O(n)  — each pointer travels the array once
     * Space: O(k)  — where k is the number of distinct characters allowed
     */
    public static int findLongest(String text, int maxDistinct) {
        if (text == null || text.isEmpty() || maxDistinct == 0) return 0;

        Map<Character, Integer> charFrequencyInWindow = new HashMap<>();
        int leftPointer = 0, longestFound = 0;

        for (int rightPointer = 0; rightPointer < text.length(); rightPointer++) {
            char incomingChar = text.charAt(rightPointer);
            charFrequencyInWindow.put(incomingChar, charFrequencyInWindow.getOrDefault(incomingChar, 0) + 1);

            // Shrink from the left until we're back to maxDistinct distinct chars
            while (charFrequencyInWindow.size() > maxDistinct) {
                char outgoingChar = text.charAt(leftPointer);
                charFrequencyInWindow.put(outgoingChar, charFrequencyInWindow.get(outgoingChar) - 1);

                if (charFrequencyInWindow.get(outgoingChar) == 0) {
                    charFrequencyInWindow.remove(outgoingChar);
                }
                leftPointer++;
            }

            longestFound = Math.max(longestFound, rightPointer - leftPointer + 1);
        }

        return longestFound;
    }

    public static void main(String[] args) {
        String dnaSequence = "AABABCBCBAABC";
        int result = findLongest(dnaSequence, 2);
        System.out.println("DNA sequence: " + dnaSequence);
        System.out.println("Longest valid substring length (2 distinct): " + result);
    }
}

package io.thecodeforge.algorithms;

public class MinSizeSubarraySum {

    /**
     * Finds the minimum length of a contiguous subarray whose sum is >= targetSum.
     * Time:  O(n)
     * Space: O(1)
     */
    public static int minSubarrayLength(int[] nums, int targetSum) {
        int leftPointer = 0, currentWindowSum = 0;
        int minimumLength = Integer.MAX_VALUE;

        for (int rightPointer = 0; rightPointer < nums.length; rightPointer++) {
            currentWindowSum += nums[rightPointer];

            // Update the answer INSIDE this loop — that's the minimum-problem pattern
            while (currentWindowSum >= targetSum) {
                minimumLength = Math.min(minimumLength, rightPointer - leftPointer + 1);
                currentWindowSum -= nums[leftPointer];
                leftPointer++;
            }
        }

        return (minimumLength == Integer.MAX_VALUE) ? 0 : minimumLength;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 2, 4, 3};
        int target = 7;
        System.out.println("Input: " + java.util.Arrays.toString(nums) + ", Target: " + target);
        System.out.println("Minimum length: " + minSubarrayLength(nums, target));
    }
}

package io.thecodeforge.algorithms;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Simulates a sliding window over a stream of data.
 * This mimics how production systems track rolling averages or rate limits.
 */
public class StreamSlidingWindow {
    private final int windowSize;
    private final Queue<Integer> window = new LinkedList<>();
    private double runningSum = 0;

    public StreamSlidingWindow(int size) {
        this.windowSize = size;
    }

    public void addReading(int val) {
        window.add(val);
        runningSum += val;

        if (window.size() > windowSize) {
            runningSum -= window.poll();
        }
    }

    public double getRollingAverage() {
        return window.isEmpty() ? 0 : runningSum / window.size();
    }

    public static void main(String[] args) {
        StreamSlidingWindow throughputTracker = new StreamSlidingWindow(3);
        int[] streamData = {100, 200, 300, 400, 500};

        for (int data : streamData) {
            throughputTracker.addReading(data);
            System.out.println("Added: " + data + " | Current Rolling Avg: " + throughputTracker.getRollingAverage());
        }
    }
}

package io.thecodeforge.algorithms;

import java.util.ArrayDeque;
import java.util.Deque;

public class SlidingWindowMaximum {

    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) return new int[0];
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>(); // stores indices

        for (int i = 0; i < n; i++) {
            // Remove indices outside current window
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            // Maintain decreasing order: remove smaller values from back
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);

            // Record maximum when window is complete
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int[] maxes = maxSlidingWindow(nums, k);
        System.out.println("Sliding window maximums: " + java.util.Arrays.toString(maxes));
    }
}