Elemento que ocurre consecutivamente en un subarreglo dado más o igual a K veces

Dada una array de consultas de tamaño N y Q, cada consulta consta de L, R y K (considere una indexación basada en 1 para L y R). La tarea es encontrar un elemento para cada consulta que ocurre consecutivamente en el subarreglo [L, R] más o igual a K veces. K siempre será mayor que floor((R-L+1)/2) . Si no existe tal elemento, imprima -1.
Ejemplos: 
 

Entrada: arr[] = [1, 3, 3, 3, 4] 
Q = 1 
L = 1, R = 5, K = 3 
Salida: 3 
El elemento 3 aparece 3 veces consecutivas en el rango [1, 5]
Entrada : arr[] = [3, 2, 1, 1, 2, 2, 2, 2] 
Q = 2 
L = 2, R = 6, K = 3 
L = 3, R = 8, K = 4 
Salida: 
– 1 
2

Enfoque: cree dos arrays auxiliares izquierda y derecha de tamaño n. La array izquierda almacenará el recuento de elementos desde el inicio que se produce de forma consecutiva en la array. La array de la derecha almacenará el conteo de elementos desde atrás que ocurren consecutivamente en la array. Dado que en la pregunta se da que k siempre será mayor que floor((R-L+1)/2) . Por lo tanto, si existe algún elemento de este tipo en el rango dado, siempre se encuentra en el índice medio . Matemáticamente, min{ derecha[media] + media – 1, r – 1 }-max{ media – izquierda[media] + 1, l – 1} + 1dará el rango del elemento en el subarreglo LR que se encuentra en el índice medio. Si el rango excede o es igual a k, devuelve el elemento a[mid]. Si no es así, devuelve -1. 
A continuación se muestra la implementación del enfoque anterior: 
 

// CPP program to find the element for each
// query that occurs consecutively in the
// subarray [L, R] more than or equal to K times.
#include <bits/stdc++.h>
using namespace std;
 
/// Function to find the element for each
/// query that occurs consecutively in the
/// subarray [L, R] more than or equal to K times.
int findElement(int arr[], int left[], int right[],
                int n, int l, int r, int k)
{
    // find mid point of subarray [L, R]
    int mid = (l - 1 + r - 1) / 2;
 
    // find starting and ending index of range
    int s = max(mid - left[mid] + 1, l - 1);
    int e = min(right[mid] + mid - 1, r - 1);
 
    int range = e - s + 1;
 
    // compare this range with k
    // if it is greater than or
    // equal to k, return element
    if (range >= k)
        return arr[mid];
    // if not then return -1
    else
        return -1;
}
 
// function to answer query in range [L, R]
int answerQuery(int arr[], int n, int l, int r, int k)
{
    int left[n], right[n];
 
    // store count of elements that occur
    // consecutively in the array [1, n]
    int count = 1;
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] == arr[i + 1]) {
            left[i] = count;
            count++;
        }
        else {
            left[i] = count;
            count = 1;
        }
    }
    left[n - 1] = count;
 
    // store count of elements that occur
    // consecutively in the array [n, 1]
    count = 1;
    for (int i = n - 1; i > 0; i--) {
        if (arr[i] == arr[i - 1]) {
            right[i] = count;
            count++;
        }
        else {
            right[i] = count;
            count = 1;
        }
    }
    right[0] = count;
 
    // Function to return the element
    return findElement(arr, left, right, n, l, r, k);
}
 
// Driver Code
int main()
{
    int a[] = { 3, 2, 1, 1, 2, 2, 2, 2 };
    int n = sizeof(a) / sizeof(a[0]);
 
    // 1st query
    int L = 2, R = 6, k = 3;
    cout << answerQuery(a, n, L, R, k) << "\n";
 
    // 2nd query
    L = 3, R = 8, k = 4;
    cout << answerQuery(a, n, L, R, k);
}

// Java program to find the element for each
// query that occurs consecutively in the
// subarray [L, R] more than or equal to K times.
import java.util.*;
 
class solution
{
 
/// Function to find the element for each
/// query that occurs consecutively in the
/// subarray [L, R] more than or equal to K times.
static int findElement(int[] arr, int[] left, int[] right,
                int n, int l, int r, int k)
{
    // find mid point of subarray [L, R]
    int mid = (l - 1 + r - 1) / 2;
 
    // find starting and ending index of range
    int s = Math.max(mid - left[mid] + 1, l - 1);
    int e = Math.min(right[mid] + mid - 1, r - 1);
 
    int range = e - s + 1;
 
    // compare this range with k
    // if it is greater than or
    // equal to k, return element
    if (range >= k)
        return arr[mid];
    // if not then return -1
    else
        return -1;
}
 
// function to answer query in range [L, R]
static int answerQuery(int arr[], int n, int l, int r, int k)
{
    int[] left = new int[n];
    int[] right = new int[n];
 
    // store count of elements that occur
    // consecutively in the array [1, n]
    int count = 1;
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] == arr[i + 1]) {
            left[i] = count;
            count++;
        }
        else {
            left[i] = count;
            count = 1;
        }
    }
    left[n - 1] = count;
 
    // store count of elements that occur
    // consecutively in the array [n, 1]
    count = 1;
    for (int i = n - 1; i > 0; i--) {
        if (arr[i] == arr[i - 1]) {
            right[i] = count;
            count++;
        }
        else {
            right[i] = count;
            count = 1;
        }
    }
    right[0] = count;
 
    // Function to return the element
    return findElement(arr, left, right, n, l, r, k);
}
 
// Driver Code
public static void main(String args[])
{
    int[] a = { 3, 2, 1, 1, 2, 2, 2, 2 };
    int n = a.length;
 
    // 1st query
    int L = 2, R = 6, k = 3;
    System.out.println(answerQuery(a, n, L, R, k));
 
    // 2nd query
    L = 3;
    R = 8;
    k = 4;
    System.out.println(answerQuery(a, n, L, R, k));
}
 
}
// This code is contributed by
// Shashank_Sharma

# Python3 program to find the element for each
# query that occurs consecutively in the
# subarray [L, R] more than or equal to K times.
 
# Function to find the element for each
# query that occurs consecutively in the
# subarray [L, R] more than or equal to K times.
def findElement(arr, left, right, n, l, r, k):
  
    # find mid point of subarray [L, R]
    mid = (l - 1 + r - 1) // 2
 
    # find starting and ending index of range
    s = max(mid - left[mid] + 1, l - 1)
    e = min(right[mid] + mid - 1, r - 1)
 
    _range = e - s + 1
 
    # compare this range with k
    # if it is greater than or
    # equal to k, return element
    if _range >= k:
        return arr[mid]
    # if not then return -1
    else:
        return -1
 
# function to answer query in range [L, R]
def answerQuery(arr, n, l, r, k):
  
    left, right = [None] * n, [None] * n
 
    # store count of elements that occur
    # consecutively in the array [1, n]
    count = 1
    for i in range(0, n - 1): 
        if arr[i] == arr[i + 1]: 
            left[i] = count
            count += 1
          
        else:
            left[i] = count
            count = 1
          
    left[n - 1] = count
 
    # store count of elements that occur
    # consecutively in the array [n, 1]
    count = 1
    for i in range(n - 1, 0, -1): 
        if arr[i] == arr[i - 1]: 
            right[i] = count
            count += 1
          
        else:
            right[i] = count
            count = 1
          
    right[0] = count
 
    # Function to return the element
    return findElement(arr, left, right, n, l, r, k)
  
# Driver Code
if __name__ == "__main__":
  
    a = [3, 2, 1, 1, 2, 2, 2, 2] 
    n = len(a)
 
    # 1st query
    L, R, k = 2, 6, 3
    print(answerQuery(a, n, L, R, k))
 
    # 2nd query
    L, R, k = 3, 8, 4
    print(answerQuery(a, n, L, R, k))
  
# This code is contributed by Rituraj Jain

// C# program to find the element for each
// query that occurs consecutively in the
// subarray [L, R] more than or equal to K times.
using System;
 
class GFG
{
     
// Function to find the element for each
// query that occurs consecutively in the
// subarray [L, R] more than or equal to K times.
static int findElement(int[] arr, int[] left, int[] right,
                int n, int l, int r, int k)
{
    // find mid point of subarray [L, R]
    int mid = (l - 1 + r - 1) / 2;
 
    // find starting and ending index of range
    int s = Math.Max(mid - left[mid] + 1, l - 1);
    int e = Math.Min(right[mid] + mid - 1, r - 1);
 
    int range = e - s + 1;
 
    // compare this range with k
    // if it is greater than or
    // equal to k, return element
    if (range >= k)
        return arr[mid];
         
    // if not then return -1
    else
        return -1;
}
 
// function to answer query in range [L, R]
static int answerQuery(int []arr, int n,
                        int l, int r, int k)
{
    int[] left = new int[n];
    int[] right = new int[n];
 
    // store count of elements that occur
    // consecutively in the array [1, n]
    int count = 1;
    for (int i = 0; i < n - 1; i++)
    {
        if (arr[i] == arr[i + 1])
        {
            left[i] = count;
            count++;
        }
        else
        {
            left[i] = count;
            count = 1;
        }
    }
    left[n - 1] = count;
 
    // store count of elements that occur
    // consecutively in the array [n, 1]
    count = 1;
    for (int i = n - 1; i > 0; i--)
    {
        if (arr[i] == arr[i - 1])
        {
            right[i] = count;
            count++;
        }
        else
        {
            right[i] = count;
            count = 1;
        }
    }
    right[0] = count;
 
    // Function to return the element
    return findElement(arr, left, right, n, l, r, k);
}
 
// Driver Code
static public void Main ()
{
     
    int[] a = { 3, 2, 1, 1, 2, 2, 2, 2 };
    int n = a.Length;
     
    // 1st query
    int L = 2, R = 6, k = 3;
    Console.WriteLine(answerQuery(a, n, L, R, k));
 
    // 2nd query
    L = 3;
    R = 8;
    k = 4;
    Console.WriteLine(answerQuery(a, n, L, R, k));
}
}
 
// This code is contributed by ajit..

<script>
 
// Javascript program to find the element for each
// query that occurs consecutively in the
// subarray [L, R] more than or equal to K times.
 
/// Function to find the element for each
/// query that occurs consecutively in the
/// subarray [L, R] more than or equal to K times.
function findElement(arr, left, right,
                n, l, r, k)
{
    // find mid point of subarray [L, R]
    let mid = Math.floor((l - 1 + r - 1) / 2);
   
    // find starting and ending index of range
    let s = Math.max(mid - left[mid] + 1, l - 1);
    let e = Math.min(right[mid] + mid - 1, r - 1);
   
    let range = e - s + 1;
   
    // compare this range with k
    // if it is greater than or
    // equal to k, return element
    if (range >= k)
        return arr[mid];
    // if not then return -1
    else
        return -1;
}
   
// function to answer query in range [L, R]
function answerQuery(arr, n, l, r, k)
{
    let left = new Array(n).fill(0);
    let right = new Array(n).fill(0);
   
    // store count of elements that occur
    // consecutively in the array [1, n]
    let count = 1;
    for (let i = 0; i < n - 1; i++) {
        if (arr[i] == arr[i + 1]) {
            left[i] = count;
            count++;
        }
        else {
            left[i] = count;
            count = 1;
        }
    }
    left[n - 1] = count;
   
    // store count of elements that occur
    // consecutively in the array [n, 1]
    count = 1;
    for (let i = n - 1; i > 0; i--) {
        if (arr[i] == arr[i - 1]) {
            right[i] = count;
            count++;
        }
        else {
            right[i] = count;
            count = 1;
        }
    }
    right[0] = count;
   
    // Function to return the element
    return findElement(arr, left, right, n, l, r, k);
}
 
// driver program
     
    let a = [ 3, 2, 1, 1, 2, 2, 2, 2 ];
    let n = a.length;
   
    // 1st query
    let L = 2, R = 6, k = 3;
    document.write(answerQuery(a, n, L, R, k) + "<br/>" );
   
    // 2nd query
    L = 3;
    R = 8;
    k = 4;
    document.write(answerQuery(a, n, L, R, k));
   
</script>

-1
2

Complejidad de tiempo: O(N) para calcular previamente la array izquierda y derecha y O(1) para responder a cada consulta. 
Espacio Auxiliar: O(N)