Make K Most Frequent
Source: codechef
Difficulty: 1637

Make K Most Frequent
You are given an array$A$of$N$integers. You can perform the following operation any number of times:
Select and remove any prefix or suffix of the array$A$, but not the entire array.
Your goal is to determine the minimum number of operations required to make$K$the most frequent element in the array$A$.
It is guaranteed that$K$is initially present in the array$A$.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of two lines of input.
The first line of each test case contains two space-separated integers$N$and$K$— denoting the length of the array$A$and the target number, which you want to make the most frequent element in the array, respectively.
The second line contains$N$space-separated integers$A_1, A_2, A_3, \ldots, A_N$, denoting the array$A$.
Output Format
For each test case, output on a new line the minimum number of operations required to make$K$the most frequent number in the array.
Constraints$1 \leq T \leq 10^5$$1 \leq N \leq 10^4$$1 \leq K,A_i \leq 20$It is guaranteed that$K$is present in the array$A$.
The sum of$N$over all test cases does not exceed$2 \cdot 10^5$.
Sample 1:
Explanation:
Test case$1$:
: Since$1$is already the most frequent, we don't need to perform any operations.
Test case$2$:
: Since$2$is already the most frequent, we don't need to perform any operations.
Test case$3$:
: Since$1$is already the most frequent, we don't need to perform any operations.
Test case$4$:
:$[\underline{2, 2}, 1, 2] \xrightarrow{\text{Delete prefix from } l=1 \text{ to } r=2} [1, 2]$. Since$1$is now the most frequent, we don't need to perform any operations. The total number of operations will be$1$.
Test case$5$:
:$[\underline{1, 1}, 3, 2, 2] \xrightarrow{\text{Delete prefix from } l=1 \text{ to } r=2} [3, 2, 2]$.$[3, \underline{2, 2}] \xrightarrow{\text{Delete suffix from } l=2 \text{ to } r=3} [3]$. Since$3$is now the most frequent, we don't need to perform any operations. The total number of operations will be$2$.

Sample Input:
5
1 1
1
2 2
1 2
2 1
1 2
4 1
2 2 1 2
5 3
1 1 3 2 2

Sample Output:
0
0
0
1
2

C++ solution:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define f(i, n) for (ll i = 0; i < n; i++)
#define ia(a, n) \
    ll a[n];     \
    f(i, n) cin >> a[i]
#define iv(v, n)     \
    vector<ll> v(n); \
    f(i, n) cin >> v[i]
#define MOD (1000000007)
#define INF 1000000000000000000LL // Infinity for ll
#define mp make_pair
#define nline '\n'
#define yes cout << "YES\n"
#define no cout << "NO\n"

template <typename T>
using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T>
using oms = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

// read question properly
// don't forget newlines!!!!!!
// take care about cin >> t;
// comment the optimization before debugging
// ALWAYS USE FIXED << SETPRECISION WHILE OUTPUTTING FLOATS

void solve()
{
    ll n, k;
    cin >> n >> k;
    ia(a, n);
    vector<ll> fr(21);
    f(i, n)
    {
        fr[a[i]]++;
    }
    if (*max_element(fr.begin(), fr.end()) == fr[k])
    {
        cout << 0 << nline;
        return;
    }
    // prefix
    {
        auto temp = fr;
        f(i, n)
        {
            fr[a[i]]--;
            if (fr[k] == 0)
                break;
            if (*max_element(fr.begin(), fr.end()) == fr[k])
            {
                cout << 1 << nline;
                return;
            }
        }
        fr = temp;
    }

    // suffix
    {
        auto temp = fr;
        for (ll i = n - 1; i >= 0; i--)
        {
            fr[a[i]]--;
            if (fr[k] == 0)
            {
                break;
            }
            if (*max_element(fr.begin(), fr.end()) == fr[k])
            {
                cout << 1 << nline;
                return;
            }
        }
        fr = temp;
    }
    cout << 2 << nline;
}

int main()
{
#ifdef PRADY
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    clock_t T = clock();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long long t = 1;
    cin >> t;

    while (t--)
    {
        solve();
    }

#ifdef PRADY
    cout << "\nTime taken: " << ((float)(clock() - T)) / CLOCKS_PER_SEC << " seconds";
#endif
    return 0;
}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    // Reading input
    reader := bufio.NewReader(os.Stdin)
    writer := bufio.NewWriter(os.Stdout)
    defer writer.Flush()

    // Read number of test cases
    tStr, _ := reader.ReadString('\n')
    testCases, _ := strconv.Atoi(strings.TrimSpace(tStr))

    for t := 0; t < testCases; t++ {
        // Read sizes and target
        line, _ := reader.ReadString('\n')
        data := strings.Fields(line)
        sizes, _ := strconv.Atoi(data[0])
        target, _ := strconv.Atoi(data[1])

        // Read array elements
        line, _ = reader.ReadString('\n')
        elementsStr := strings.Fields(line)
        elements := make([]int, sizes)
        for i, val := range elementsStr {
            elements[i], _ = strconv.Atoi(val)
        }

        // Frequency count for the entire array
        freq := make([]int, 21)
        for _, el := range elements {
            freq[el]++
        }

        // Check if the target is already most frequent
        isFullOK := true
        for value := 1; value <= 20; value++ {
            if value == target {
                continue
            }
            if freq[target] < freq[value] {
                isFullOK = false
                break
            }
        }

        if isFullOK {
            fmt.Fprintln(writer, 0)
            continue
        }

        // Check prefix deletions
        prefixFreq := make([]int, 21)
        found := false
        for i := 0; i < sizes-1; i++ {
            prefixFreq[elements[i]]++
            if prefixFreq[target] == 0 {
                continue
            }
            isValid := true
            for value := 1; value <= 20; value++ {
                if value == target {
                    continue
                }
                if prefixFreq[target] < prefixFreq[value] {
                    isValid = false
                    break
                }
            }
            if isValid {
                fmt.Fprintln(writer, 1)
                found = true
                break
            }
        }
        if found {
            continue
        }

        // Check suffix deletions
        suffixFreq := make([]int, 21)
        for i := sizes - 1; i >= 0; i-- {
            suffixFreq[elements[i]]++
            if suffixFreq[target] == 0 {
                continue
            }
            isValid := true
            for value := 1; value <= 20; value++ {
                if value == target {
                    continue
                }
                if suffixFreq[target] < suffixFreq[value] {
                    isValid = false
                    break
                }
            }
            if isValid {
                fmt.Fprintln(writer, 1)
                found = true
                break
            }
        }
        if !found {
            fmt.Fprintln(writer, 2)
        }
    }
}

Java solution:
/**
 * @author Abhisek Singh (Zyroßeast)
 * 
 */

import java.io.DataInputStream;
import java.io.IOException;
import java.util.HashMap;

public class Main {

   /**
    * Main logic for the program.
    * 
    * @param args Not Used anywhere
    * @throws IllegalArgumentException If any Error happens while processing data.
    * 
    */
    public static void main(String[] args) throws IllegalArgumentException {
        initializeIO();
        try {
            int __ = nextInt(), n, k, arr[], i, max;
            HashMap<Integer, Integer> map = new HashMap<>();
  
            while(__ -- > 0) {
                n = nextInt(); k = nextInt();
                arr = new int[n];
                map.clear();
                
                for (i = 0, max = 0; i < n; i++) {
                    arr[i] = nextInt();
                    map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
                    max = Math.max(max, map.get(arr[i]));
                }
                
                if(map.get(k) == max) {
                    outData.append("0\n");
                    continue;
                }
                
                map.clear();
                for(i = 0, max = 0; i < n; i++) {
                    map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
                    max = Math.max(max, map.get(arr[i]));
                    if(map.getOrDefault(k, 0) == max)  break;
                }
                
                if (i < n) {
                    outData.append("1\n");
                    continue;
                }
                
                map.clear();
                for(i = n - 1, max = 0; i >= 0; i--) {
                    map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
                    max = Math.max(max, map.get(arr[i]));
                    if(map.getOrDefault(k, 0) == max)  break;
                }
                
                if (i >= 0) {
                    outData.append("1\n");
                    continue;
                }
                
                
                outData.append("2\n");
            }
        
        } catch(IllegalArgumentException iae) {
            close();
            throw iae;
        }
        
        close();
    }
    
    
    
    
    
    
    
    
    
    
   /* The methods below are used for low level IO operations
    that will be used in the program. */
     
   /** InputStream with implemented buffering for faster input */
    private static DataInputStream dis;
   /** Buffer for input */
    private static byte[] buffer;
   /** Variables for reading buffer */
    private static int bytesRead, bufferPos;
   /** Unsynchronized Mutable String to store Output */
    private static StringBuilder outData;
    
   /**
    * Initializes the IO objects.
    * To be called before using IO methods.
    * 
    */
    private static void initializeIO() {
        dis = new DataInputStream(System.in);
        buffer = new byte[1 << 16];
        read();
        
        outData = new StringBuilder();
    }
    
   /**
    * Closes IO objects after execution.
    * 
    */
    private static void close() {
        try {
            System.out.print(outData);
            dis.close();
        }
        catch(IOException e) {
        }
    }
    
   /** To store next byte in buffer for Operations. */
    private static byte c;
   /** To store if a integer type data is negative or not. */
    private static boolean neg;
    
   /**
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * 
    * @return The next Integer data from the input data
    * 
    */
    private static int nextInt() throws IllegalArgumentException {
        skipWhiteSpace();
        int temp = 0;
        
        neg = (c == '-');
        if(neg) {
            read();
        }

        do {
            if(!isDigit()) {
                throw new IllegalArgumentException();
            }
            
            temp = temp * 10 + c - '0';
            read();
        } while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1));
        
        return neg ? -temp : temp;
    }
    
   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * @return The Integer array with the specified number of elements.
    * 
    */
    private static int[] nextIntArr(int n) throws IllegalArgumentException {
        int[] arr = new int[n];
        for(int i = 0; i < n; i ++) arr[i] = nextInt();
        return arr;
    }
    
   /**
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * 
    * @return The next Long data in the input data
    * 
    */
    private static long nextLong() throws IllegalArgumentException {
        skipWhiteSpace();
        long temp = 0;

        neg = (c == '-');
        if (neg) {
            read();
        }
        
        do {
            if(!isDigit()) {
                throw new IllegalArgumentException();
            }
            
            temp = temp * 10L + c - '0';
            read();
        } while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1));

        return neg ? -temp : temp;
    }

   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an long type.
    * @return The Long array with the specified number of elements.
    * 
    */
    private static long[] nextLongArr(int n) throws IllegalArgumentException {
        long[] arr = new long[n];
        for(int i = 0; i < n; i ++) arr[i] = nextLong();
        return arr;
    }
    
   /**
    * @throws IllegalArgumentException If the next input data is not float or integer.
    * 
    * @return The next Double data in the input stream.
    * 
    */
    private static double nextDouble() {
        skipWhiteSpace();
        double temp = 0.0d;
        
        neg = (c == '-');
        if(neg) {
            read();
        }
        
        if(c != '.') {
            do {
                if(!isDigit()) {
                    throw new IllegalArgumentException();
                }
            
                temp = temp * 10.0d + c - '0';
                read();
            } while(c != '.' && !(c == '\n' || c == ' ' || c == '\r') && (c != -1));
        }
        
        if(c == '.') {
            double div = 1.0d;
            read();
            
            while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1)) {
                if(!isDigit()) {
                    throw new IllegalArgumentException();
                }
            
                temp = temp * 10.0d + c - '0';
                div *= 10.0d;
                read();
            }
            
            temp /= div;
        }
        
        return neg ? -temp : temp;
    }

   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an double type.
    * @return The Double array with the specified number of elements.
    * 
    */
    private static double[] nextDoubleArr(int n) throws IllegalArgumentException {
        double[] arr = new double[n];
        for(int i = 0; i < n; i ++) arr[i] = nextDouble();
        return arr;
    }
    
   /**
    * Checks if a byte is number or not.
    * 
    */
    private static boolean isDigit() {
        return (c >= '0' && c <= '9');
    }
  
   /** Stores the initial length of the given StringBuilder in the following functions. */
    private static int length;
   
   /**
    * Writes the remaining data from the current line from the input data in the given StringBuilder.
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @throws IllegalArgumentException If there is no byte left in input data.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder getLine(StringBuilder sb) throws IllegalArgumentException {
        sb.setLength(0);
        
        while(c != -1) {
            if(c == '\n' || c == '\r') {
                break;
            }
            
            sb.append((char)c);
            read();
        }
        
        if(sb.length() == 0) {
            throw new IllegalArgumentException();
        }
        
        return sb;
    }
    
   /**
    * Writes the next line from the current line from the input data in the given StringBuilder.
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder nextLine(StringBuilder sb) {
        skipLine(); getLine(sb);
        return sb;
    }
    
   /**
    * Appends the next word from the input data in the given StringBuilder
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @throws IllegalArgumentException If there is no byte left in input data.
    * @return The StringBuilder object after filling it.
    *
    */
    private static StringBuilder addNext(StringBuilder sb) throws IllegalArgumentException {
        skipWhiteSpace();
        length = sb.length();
        
        while(c != -1) {
            if(c == ' ' || c == '\n' || c == '\r') {
                break;
            }
            
            sb.append((char)c);
            read();
        }
        
        if(sb.length() == length) {
            throw new IllegalArgumentException();
        }
        
        return sb;
    }
    
   /**
    * Writes the next word from the input data in the given StringBuilder
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder next(StringBuilder sb) {
        sb.setLength(0);
        addNext(sb);
        return sb;
    }
    
   /**
    * Skips any prevailing space or empty lines.
    * 
    */ 
    private static void skipWhiteSpace() {
        while((c == '\n' || c == ' ' || c == '\r') && (c != -1)) {
            read();
        }
    }
   
   /**
    * Skips any prevailing space.
    * 
    */
    private static void skipSpace() {
        while(c == ' ' && c != -1) {
            read();
        }
    }
     
   /**
    * Skips a line from the input stream.
    * 
    */
    private static void skipLine() {
        while(c != '\n' && c != '\r' && c != -1) {
            read();
        }
        
        while(c != -1 && (c == '\n' || c == '\r')) {
            read();
        }
    }
    
   /**
    * Skips a word from the input stream.
    * 
    */
    private static void skipWord() {
        while(c != '\n' && c != ' ' && c != '\r' && c != -1) {
            read();
        }
        
        read();
    }
    
   /**
    * Refills the buffer with new data.
    * 
    */
    private static void fillBuffer() throws IOException {
        bytesRead = dis.read(buffer, bufferPos = 0, buffer.length);
        
        if(bytesRead == -1) {
            buffer[0] = -1;
        }
    }
   
   /**
    * Reads the next byte from the input data and stores it in {@link c}
    * 
    */
    private static void read() {
        if(bufferPos >= bytesRead) {
            try {
                fillBuffer();
            }
            catch(IOException e) {
            }
        }
        
        c = buffer[bufferPos ++];
    }
}

JavaScript solution:
/* -------------------------------------------------------- */
/*   ( The Authentic JS CodeBuff )
 ___ _                      _              _ 
 | _ ) |_  __ _ _ _ __ _ __| |_ __ ____ _ (_)
 | _ \ ' \/ _` | '_/ _` / _` \ V  V / _` || |
 |___/_||_\__,_|_| \__,_\__,_|\_/\_/\__,_|/ |
                                        |__/ 
 */
/* ---------------------------------------------------------   */
/*    Youtube: https://youtube.com/@code-with-Bharadwaj        */
/*    Github : https://github.com/Manu577228                  */
/* ----------------------------------------------------------- */

// Template Starts here Fast IO!

let V8Flags = [
    '--max-old-space-size=4096', '--max-semi-space-size=16', '--stack-size=65536', '--reclaim-unused-memory',
    '--gc-interval=100', '--expose-gc', '--gc-global', '--optimize-for-speed',
    '--always-opt', '--max-inlined-source-size=600', '--max-inlined-bytecode-size=600', '--turbo-inline-js-wasm-calls',
    '--turbo', '--turbo-optimizer', '--force-optimization', '--no-lazy',
    '--no-lazy-inner-functions', '--optimize-for-size', '--initial-heap-size=64', '--max-heap-size=192',
    '--use-strict', '--predictable', '--single-threaded-gc', '--no-inline-new',
    '--opt', '--no-lazy-deserialization', '--no-browser-globals', '--turbo-inline-array-builtins',
    '--fast-math', '--fuzzing', '--minor-mc', '--incremental-marking',
    '--concurrent-recompilation', '--stress-compaction', '--experimental-flush-embedded-blob-icache', '--experimental-value-unavailable'
];

if (V8Flags.length > 0) {
        process.execArgv.push('--v8-options=' + V8Flags.join(' '));
}

let i = Buffer.allocUnsafe(1e7);
let p = 0,
        l = 0;
let o = Buffer.allocUnsafe(1e7);
let q = 0;

let f = require('fs');
l = f.readSync(process.stdin.fd, i, 0, i.length, null);

let r = () => {
        let n = 0,
                s = 1;
        while (i[p] < 48 || i[p] > 57) {
                if (i[p] === 45) s = -1;
                p++;
        }
        while (p < l && i[p] >= 48 && i[p] <= 57) {
                n = n * 10 + (i[p++] - 48);
        }
        return n * s;
};

let x = true;
let w = (v, e = false) => {
        if (!x) o[q++] = 32;
        if (v < 0) {
                o[q++] = 45;
                v = -v;
        }
        let d = [];
        do {
                d.push(v % 10);
                v = Math.floor(v / 10);
        } while (v > 0);
        for (let j = d.length - 1; j >= 0; j--) {
                o[q++] = 48 + d[j];
        }
        x = e;
        if (e) {
                o[q++] = 10;
                x = true;
        }
};

// Template Ends here!

let z = (n, c, a) => {
        let f = new Uint32Array(21);
        for (let x of a) f[x]++;
        for (let v = 1; v < 21; v++) {
                if (v === c) continue;
                if (f[c] < f[v]) return false;
        }
        return true;
};

let y = (n, c, a) => {
        let g = new Uint32Array(21);
        for (let j = 0; j < n - 1; j++) {
                g[a[j]]++;
                if (g[c] === 0) continue;
                let b = true;
                for (let v = 1; v < 21; v++) {
                        if (v !== c && g[c] < g[v]) {
                                b = false;
                                break;
                        }
                }
                if (b) return true;
        }
        
        let h = new Uint32Array(21);
        for (let j = n - 1; j > 0; j--) {
                h[a[j]]++;
                if (h[c] === 0) continue;
                let b = true;
                for (let v = 1; v < 21; v++) {
                        if (v !== c && h[c] < h[v]) {
                                b = false;
                                break;
                        }
                }
                if (b) return true;
        }
        return false;
};

let t = r();
while (t--) {
        let n = r(),
                k = r();
        let a = [];
        for (let j = 0; j < n; j++) a.push(r());
        if (z(n, k, a)) w(0, true);
        else if (y(n, k, a)) w(1, true);
        else w(2, true);
}

f.writeSync(process.stdout.fd, o.slice(0, q));

Python solution:
def main():
    t = int(input())  # Read the number of test cases
    for _ in range(t):
        n, k = map(int, input().split())  # Read n and k
        v = list(map(int, input().split()))  # Read the vector v
        
        m = {}
        ans = 0
        
        # First pass to find the most frequent element
        for i in range(n):
            m[v[i]] = m.get(v[i], 0) + 1
            ans = max(ans, m[v[i]])

        # If the maximum frequency of any element is equal to the frequency of k
        if ans == m.get(k, 0):
            print(0)
        else:
            m.clear()
            ct = 0
            pt = 0

            # Second pass from left to right
            for i in range(n):
                m[v[i]] = m.get(v[i], 0) + 1
                ct = max(ct, m[v[i]])
                if ct == m.get(k, 0):
                    pt = 1
                    break

            m.clear()
            ct = 0

            # Third pass from right to left
            for i in range(n - 1, -1, -1):
                m[v[i]] = m.get(v[i], 0) + 1
                ct = max(ct, m[v[i]])
                if ct == m.get(k, 0):
                    pt = 1
                    break

            if pt:
                print(1)
            else:
                print(2)

if __name__ == "__main__":
    main()

Ruby solution:
def min_operations(n, k, arr)
  # Count frequency of each element
  freq = Hash.new(0)
  arr.each { |num| freq[num] += 1 }
  
  # Check if k is already most frequent
  max_freq = freq.values.max
  return 0 if freq[k] == max_freq
  
  # Check prefixes
  prefix_freq = Hash.new(0)
  arr.each_with_index do |num, i|
    prefix_freq[num] += 1
    if num == k
      current_max = prefix_freq.values.max
      return 1 if prefix_freq[k] == current_max
    end
  end
  
  # Check suffixes
  suffix_freq = Hash.new(0)
  (n-1).downto(0) do |i|
    suffix_freq[arr[i]] += 1
    if arr[i] == k
      current_max = suffix_freq.values.max
      return 1 if suffix_freq[k] == current_max
    end
  end
  
  # Default to 2 operations if needed
  2
end

# Read input and process
input = $stdin.read.split("\n")
test_cases = input[0].to_i
index = 1

test_cases.times do
  n, k = input[index].split.map(&:to_i)
  index += 1
  arr = input[index].split.map(&:to_i)
  index += 1
  puts min_operations(n, k, arr)
end