Queue -- Optimization Exercises¶

// O(n*k): scan each window for maximum
public static int[] maxSlidingWindow(int[] nums, int k) {
    int[] result = new int[nums.length - k + 1];
    for (int i = 0; i <= nums.length - k; i++) {
        int max = nums[i];
        for (int j = i + 1; j < i + k; j++) {
            max = Math.max(max, nums[j]);
        }
        result[i] = max;
    }
    return result;
}

// O(n): monotonic deque -- each element is added/removed at most once
public static int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> dq = new ArrayDeque<>();  // stores indices
    int[] result = new int[nums.length - k + 1];
    int idx = 0;

    for (int i = 0; i < nums.length; i++) {
        if (!dq.isEmpty() && dq.peekFirst() <= i - k) {
            dq.pollFirst();
        }
        while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
            dq.pollLast();
        }
        dq.offerLast(i);
        if (i >= k - 1) {
            result[idx++] = nums[dq.peekFirst()];
        }
    }
    return result;
}

// O(n * m): simulate each time slot
public int leastInterval(char[] tasks, int n) {
    Map<Character, Integer> freq = new HashMap<>();
    for (char t : tasks) freq.merge(t, 1, Integer::sum);

    int time = 0;
    while (!freq.isEmpty()) {
        List<Map.Entry<Character, Integer>> sorted = new ArrayList<>(freq.entrySet());
        sorted.sort((a, b) -> b.getValue() - a.getValue());

        int cycle = n + 1;
        int executed = 0;
        for (var entry : sorted) {
            if (cycle <= 0) break;
            entry.setValue(entry.getValue() - 1);
            if (entry.getValue() == 0) freq.remove(entry.getKey());
            executed++;
            cycle--;
        }
        time += freq.isEmpty() ? executed : n + 1;
    }
    return time;
}

// O(n): math formula based on max frequency
public int leastInterval(char[] tasks, int n) {
    int[] freq = new int[26];
    for (char t : tasks) freq[t - 'A']++;
    int maxFreq = 0, maxCount = 0;
    for (int f : freq) {
        if (f > maxFreq) { maxFreq = f; maxCount = 1; }
        else if (f == maxFreq) maxCount++;
    }
    int intervals = (maxFreq - 1) * (n + 1) + maxCount;
    return Math.max(intervals, tasks.length);
}

// Memory leak: dequeued elements are never freed
public class LeakyQueue {
    private Object[] data = new Object[16];
    private int front = 0, rear = 0;

    public void enqueue(Object val) {
        if (rear == data.length) {
            data = Arrays.copyOf(data, data.length * 2);
        }
        data[rear++] = val;
    }

    public Object dequeue() {
        return data[front++];  // old reference stays in array!
    }
}

// Fixed: null out dequeued slots + use circular buffer
public class FixedQueue {
    private Object[] data;
    private int front = 0, size = 0, capacity;

    public FixedQueue(int cap) {
        this.capacity = cap;
        this.data = new Object[cap];
    }

    public void enqueue(Object val) {
        if (size == capacity) resize(capacity * 2);
        data[(front + size) % capacity] = val;
        size++;
    }

    public Object dequeue() {
        Object val = data[front];
        data[front] = null;  // null out for GC
        front = (front + 1) % capacity;
        size--;
        return val;
    }

    private void resize(int newCap) {
        Object[] newData = new Object[newCap];
        for (int i = 0; i < size; i++)
            newData[i] = data[(front + i) % capacity];
        data = newData;
        front = 0;
        capacity = newCap;
    }
}

// High allocation: creates a new int[] for each cell in the queue
public int bfsDistance(int[][] grid, int[] start, int[] end) {
    int rows = grid.length, cols = grid[0].length;
    boolean[][] visited = new boolean[rows][cols];
    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{start[0], start[1], 0});  // each enqueue allocates
    visited[start[0]][start[1]] = true;

    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        if (cell[0] == end[0] && cell[1] == end[1]) return cell[2];
        for (int[] d : new int[][]{{0,1},{0,-1},{1,0},{-1,0}}) {
            int nr = cell[0]+d[0], nc = cell[1]+d[1];
            if (nr>=0 && nr<rows && nc>=0 && nc<cols && !visited[nr][nc] && grid[nr][nc]==0) {
                visited[nr][nc] = true;
                queue.offer(new int[]{nr, nc, cell[2]+1});
            }
        }
    }
    return -1;
}

// Low allocation: use a distance matrix instead of storing distance in queue
public int bfsDistance(int[][] grid, int[] start, int[] end) {
    int rows = grid.length, cols = grid[0].length;
    int[][] dist = new int[rows][cols];
    for (int[] row : dist) Arrays.fill(row, -1);
    dist[start[0]][start[1]] = 0;

    // Encode (r, c) as single int to avoid array allocation
    ArrayDeque<Integer> queue = new ArrayDeque<>();
    queue.offer(start[0] * cols + start[1]);

    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    while (!queue.isEmpty()) {
        int encoded = queue.poll();
        int r = encoded / cols, c = encoded % cols;
        if (r == end[0] && c == end[1]) return dist[r][c];
        for (int[] d : dirs) {
            int nr = r+d[0], nc = c+d[1];
            if (nr>=0 && nr<rows && nc>=0 && nc<cols && dist[nr][nc]==-1 && grid[nr][nc]==0) {
                dist[nr][nc] = dist[r][c] + 1;
                queue.offer(nr * cols + nc);
            }
        }
    }
    return -1;
}