Minimum Component Subset — Problem Statement & Solution Guide

#include <bits/stdc++.h>
using namespace std;

int minComponentSubset(const vector<int>& nums, const vector<int>& required) {
    unordered_map<int,int> need;
    for(int x: required) need[x] = 0; // we only care about presence
    int requiredCount = need.size();
    unordered_map<int,int> window;
    int have = 0, left = 0, best = INT_MAX;
    for(int right = 0; right < (int)nums.size(); ++right) {
        int val = nums[right];
        if(need.find(val) != need.end()) {
            window[val]++;
            if(window[val] == 1) ++have; // first occurrence in window
        }
        while(have == requiredCount && left <= right) {
            best = min(best, right - left + 1);
            int lval = nums[left];
            if(need.find(lval) != need.end()) {
                window[lval]--;
                if(window[lval] == 0) --have;
            }
            ++left;
        }
    }
    return best == INT_MAX ? -1 : best;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; if(!(cin>>n)) return 0;
    vector<int> nums(n);
    for(int &x: nums) cin>>x;
    int m; cin>>m;
    vector<int> required(m);
    for(int &x: required) cin>>x;
    cout<<minComponentSubset(nums, required)<<"\n";
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    public static int minComponentSubset(int[] nums, int[] required) {
        Set<Integer> need = new HashSet<>();
        for (int x : required) need.add(x);
        int requiredCount = need.size();
        Map<Integer, Integer> window = new HashMap<>();
        int have = 0, left = 0, best = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; ++right) {
            int val = nums[right];
            if (need.contains(val)) {
                window.put(val, window.getOrDefault(val, 0) + 1);
                if (window.get(val) == 1) have++;
            }
            while (have == requiredCount && left <= right) {
                best = Math.min(best, right - left + 1);
                int lval = nums[left];
                if (need.contains(lval)) {
                    window.put(lval, window.get(lval) - 1);
                    if (window.get(lval) == 0) have--;
                }
                left++;
            }
        }
        return best == Integer.MAX_VALUE ? -1 : best;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int[] nums = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) nums[i] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int[] required = new int[m];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) required[i] = Integer.parseInt(st.nextToken());
        System.out.println(minComponentSubset(nums, required));
    }
}

import sys
from collections import defaultdict

def min_component_subset(nums, required):
    need = set(required)
    required_count = len(need)
    window_counts = defaultdict(int)
    have = 0
    left = 0
    best = float('inf')
    for right, val in enumerate(nums):
        if val in need:
            window_counts[val] += 1
            if window_counts[val] == 1:
                have += 1
        while have == required_count and left <= right:
            best = min(best, right - left + 1)
            lval = nums[left]
            if lval in need:
                window_counts[lval] -= 1
                if window_counts[lval] == 0:
                    have -= 1
            left += 1
    return -1 if best == float('inf') else best

if __name__ == "__main__":
    data = list(map(int, sys.stdin.read().strip().split()))
    if not data:
        sys.exit(0)
    it = iter(data)
    n = next(it)
    nums = [next(it) for _ in range(n)]
    m = next(it)
    required = [next(it) for _ in range(m)]
    print(min_component_subset(nums, required))

function minComponentSubset(nums, required) {
    const need = new Map();
    for (const x of required) need.set(x, 0);
    const requiredCount = need.size;
    const window = new Map();
    let have = 0, left = 0, best = Infinity;
    for (let right = 0; right < nums.length; ++right) {
        const val = nums[right];
        if (need.has(val)) {
            window.set(val, (window.get(val) || 0) + 1);
            if (window.get(val) === 1) have++;
        }
        while (have === requiredCount && left <= right) {
            best = Math.min(best, right - left + 1);
            const lval = nums[left];
            if (need.has(lval)) {
                window.set(lval, window.get(lval) - 1);
                if (window.get(lval) === 0) have--;
            }
            ++left;
        }
    }
    return best === Infinity ? -1 : best;
}

// Driver (same format as template)
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let idx = 0;
const n = data[idx++];
const nums = data.slice(idx, idx+n); idx+=n;
const m = data[idx++];
const required = data.slice(idx, idx+m);
console.log(minComponentSubset(nums, required).toString());