Untitled

import java.util.*;

public class Solution {

    public static long getMinConversionCost(int[] product, int k) {
        int n = product.length;
        // Total number of 1s in the array
        int totalOnes = 0;
        for (int x : product) {
            if (x == 1) totalOnes++;
        }

        // If there are no 1s, cost is 0
        if (totalOnes == 0) return 0;

        // Prefix sums to calculate number of 1s in any window of size k quickly
        int[] prefixOnes = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixOnes[i + 1] = prefixOnes[i] + product[i];
        }

        // For each index i that is a '1', find the window [j, j+k-1] 
        // that contains index i and has the minimum number of 1s.
        // The cost added by this specific 1 is (min_ones_in_window - 1)
        // because the 1 itself is included in the window sum.
        
        long totalCost = 0;
        
        // Optimization: Pre-calculate the minimum 1s in any window of size k 
        // covering each position. 
        int[] minOnesInWindowForIndex = new int[n];
        Arrays.fill(minOnesInWindowForIndex, Integer.MAX_VALUE);

        // Standard sliding window to find min ones in any k-length window
        int[] windowSums = new int[n - k + 1];
        for (int i = 0; i <= n - k; i++) {
            windowSums[i] = prefixOnes[i + k] - prefixOnes[i];
        }

        // Use a sliding window minimum (Monotonic Queue) to find 
        // the best window for each index i.
        Deque<Integer> dq = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            // Remove windows that no longer cover index i
            // A window starting at 'start' covers i if start <= i and start + k - 1 >= i
            // So start must be in range [i - k + 1, i]
            while (!dq.isEmpty() && dq.peekFirst() < i - k + 1) {
                dq.pollFirst();
            }

            // Add new window starting at i (if it exists)
            if (i <= n - k) {
                while (!dq.isEmpty() && windowSums[dq.peekLast()] >= windowSums[i]) {
                    dq.pollLast();
                }
                dq.addLast(i);
            }

            if (product[i] == 1) {
                // The cost contribution of this 1 is (min ones in a window covering it) - 1
                // We subtract 1 because the 1s are removed sequentially.
                // The last 1 always costs 0.
                // Summing (remaining 1s in best window) is equivalent to:
                totalCost += (windowSums[dq.peekFirst()] - 1);
                
                // Note: The example logic implies we subtract 1 from the total 
                // pool for each step. This greedy approach of 
                // (Sum of min_window_ones) - (totalOnes) covers the progression.
            }
        }

        return totalCost;
    }

    public static void main(String[] args) {
        int[] product = {1, 1, 1, 0, 1};
        int k = 4;
        System.out.println("Minimum Cost: " + getMinConversionCost(product, k)); // Expected: 7
    }
}