Dada una array de tamaño N que contiene todos los elementos como 0 inicialmente, y una consulta Q que contiene un rango en forma de [L, R] . La tarea es modificar el arreglo agregando 1 a cada elemento en el rango [L, R] para consultas Q y luego imprimir el tamaño del subarreglo de longitud mínima que contiene todos los elementos únicos.
Nota: La indexación basada en 1 se usa en el rango [L, R].
Ejemplos:
Entrada: N = 6, Q[4][] = {{1, 3}, {4, 6}, {3, 4}, {3, 3}} Salida: 3 Explicación: Array inicial:
arr [
]
= { 0, 0, 0, 0, 0, 0 }
Consulta 1: arr actualizado[] = { 1, 1, 1, 0, 0, 0 }.
Consulta 2: arr actualizado[] = { 1, 1, 1, 1, 1, 1 }.
Consulta 3: arr actualizado[] = { 1, 1, 2, 2, 1, 1 }.
Consulta 4: arr actualizado[] = { 1, 1, 3, 2, 1, 1 }.
El subarreglo { 1, 3, 2 } es el subarreglo mínimo que contiene todos los elementos únicos. Por lo tanto, la respuesta es 3.
Entrada: N = 8, Q[6][] = {{1, 4}, {3, 4}, {4, 5}, {5, 5}, {7, 8} , {8, 8}}
Salida: 4
Explicación:
Después de procesar todas las consultas, la array se convierte en = { 1, 1, 2, 3, 2, 0, 1, 2 }.
El subarreglo { 3, 2, 0, 1 } es el subarreglo mínimo que contiene todos los elementos únicos. Por lo tanto, la respuesta es 4.
Enfoque: la idea es utilizar el concepto de array de suma de prefijos y el enfoque de dos punteros para este problema.
- La array final después de las consultas se puede calcular incrementando el valor en la array en 1 en el índice L y disminuyendo el valor en 1 en el índice R + 1 .
Processing of a Query: arr[L] += 1 arr[R + 1] -= 1
- Finalmente, calcule la suma de prefijos de la array para calcular la array final después de las consultas. Luego use el enfoque de dos punteros para obtener el subarreglo de longitud mínima que contiene todos los elementos únicos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// minimum size subarray containing
// all unique elements after processing
// the array for K queries of ranges
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum size subarray
// of all array elements
int subarrayLength(int A[], int R[][2],
int N, int M)
{
// Updating the array after
// processing each query
for (int i = 0; i < M; ++i) {
int l = R[i][0], r = R[i][1] + 1;
// Making it to 0-indexing
l--;
r--;
// Prefix sum array concept is used
// to obtain the count array
A[l]++;
if (r < N)
A[r]--;
}
// Iterating over the array
// to get the final array
for (int i = 1; i < N; ++i) {
A[i] += A[i - 1];
}
// Variable to get count
// of all unique elements
int count = 0;
// Hash to maintain previously
// occurred elements
unordered_set<int> s;
// Loop to find the all
// unique elements
for (int i = 0; i < N; ++i) {
if (s.find(A[i]) == s.end())
count++;
s.insert(A[i]);
}
// array to maintain counter
// of encountered elements
vector<int> repeat(count + 1, 0);
// variable to store answer
int ans = N;
// Using two pointers approach
int counter = 0, left = 0, right = 0;
while (right < N) {
int cur_element = A[right];
repeat[cur_element] += 1;
// Increment counter
// if occurred once
if (repeat[cur_element] == 1)
++counter;
// when all unique
// elements are found
while (counter == count) {
// update answer with
// minimum size
ans = min(ans, right - left + 1);
// decrement count of
// elements from left
cur_element = A[left];
repeat[cur_element] -= 1;
++left;
// decrement counter
if (repeat[cur_element] == 0)
--counter;
}
++right;
}
return ans;
}
// Driver code
int main()
{
int N = 8, queries = 6;
int Q[][2]
= {
{ 1, 4 }, { 3, 4 }, { 4, 5 },
{ 5, 5 }, { 7, 8 }, { 8, 8 }
};
int A[N] = { 0 };
cout << subarrayLength(A, Q, N, queries);
return 0;
}
Java
// Java implementation to find the
// minimum size subarray containing
// all unique elements after processing
// the array for K queries of ranges
import java.util.*;
class GFG{
// Function to find minimum size subarray
// of all array elements
static int subarrayLength(int A[], int R[][],
int N, int M)
{
// Updating the array after
// processing each query
for (int i = 0; i < M; ++i)
{
int l = R[i][0], r = R[i][1] + 1;
// Making it to 0-indexing
l--;
r--;
// Prefix sum array concept is used
// to obtain the count array
A[l]++;
if (r < N)
A[r]--;
}
// Iterating over the array
// to get the final array
for (int i = 1; i < N; ++i)
{
A[i] += A[i - 1];
}
// Variable to get count
// of all unique elements
int count = 0;
// Hash to maintain previously
// occurred elements
HashSet<Integer> s = new HashSet<Integer>();
// Loop to find the all
// unique elements
for (int i = 0; i < N; ++i)
{
if (!s.contains(A[i]))
count++;
s.add(A[i]);
}
// array to maintain counter
// of encountered elements
int []repeat = new int[count + 1];
// variable to store answer
int ans = N;
// Using two pointers approach
int counter = 0, left = 0, right = 0;
while (right < N)
{
int cur_element = A[right];
repeat[cur_element] += 1;
// Increment counter
// if occurred once
if (repeat[cur_element] == 1)
++counter;
// when all unique
// elements are found
while (counter == count)
{
// update answer with
// minimum size
ans = Math.min(ans,
right - left + 1);
// decrement count of
// elements from left
cur_element = A[left];
repeat[cur_element] -= 1;
++left;
// decrement counter
if (repeat[cur_element] == 0)
--counter;
}
++right;
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int N = 8, queries = 6;
int Q[][] = {{ 1, 4 }, { 3, 4 }, { 4, 5 },
{ 5, 5 }, { 7, 8 }, { 8, 8 }};
int A[] = new int[N];
System.out.print(subarrayLength(A, Q,
N, queries));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation to find the # minimum size subarray containing # all unique elements after processing # the array for K queries of ranges # Function to find minimum size subarray # of all array elements def subarrayLength(A, R, N, M): # Updating the array after # processing each query for i in range(M): l = R[i][0] r = R[i][1] + 1 # Making it to 0-indexing l -= 1 r -= 1 # Prefix sum array concept is used # to obtain the count array A[l] += 1 if (r < N): A[r] -= 1 # Iterating over the array # to get the final array for i in range(1 , N): A[i] += A[i - 1] # Variable to get count # of all unique elements count = 0 # Hash to maintain previously # occurred elements s = [] # Loop to find the all # unique elements for i in range(N): if (A[i] not in s): count += 1 s.append(A[i]) # Array to maintain counter # of encountered elements repeat = [0] * (count + 1) # Variable to store answer ans = N # Using two pointers approach counter, left, right = 0, 0, 0 while (right < N): cur_element = A[right] repeat[cur_element] += 1 # Increment counter # if occurred once if (repeat[cur_element] == 1): counter += 1 # When all unique # elements are found while (counter == count): # update answer with # minimum size ans = min(ans, right - left + 1) # Decrement count of # elements from left cur_element = A[left] repeat[cur_element] -= 1 left += 1 # Decrement counter if (repeat[cur_element] == 0): counter -= 1 right += 1 return ans # Driver code if __name__ == "__main__": N , queries = 8 , 6 Q = [ [ 1, 4 ], [ 3, 4 ], [ 4, 5 ], [ 5, 5 ], [ 7, 8 ], [ 8, 8 ] ] A = [0] * N print(subarrayLength(A, Q, N, queries)) # This code is contributed by chitranayal
C#
// C# implementation to find the
// minimum size subarray containing
// all unique elements after processing
// the array for K queries of ranges
using System;
using System.Collections.Generic;
class GFG{
// Function to find minimum size subarray
// of all array elements
static int subarrayLength(int []A, int [,]R,
int N, int M)
{
// Updating the array after
// processing each query
for(int i = 0; i < M; ++i)
{
int l = R[i, 0], r = R[i, 1] + 1;
// Making it to 0-indexing
l--;
r--;
// Prefix sum array concept is used
// to obtain the count array
A[l]++;
if (r < N)
A[r]--;
}
// Iterating over the array
// to get the readonly array
for(int i = 1; i < N; ++i)
{
A[i] += A[i - 1];
}
// Variable to get count
// of all unique elements
int count = 0;
// Hash to maintain previously
// occurred elements
HashSet<int> s = new HashSet<int>();
// Loop to find the all
// unique elements
for(int i = 0; i < N; ++i)
{
if (!s.Contains(A[i]))
count++;
s.Add(A[i]);
}
// Array to maintain counter
// of encountered elements
int []repeat = new int[count + 1];
// Variable to store answer
int ans = N;
// Using two pointers approach
int counter = 0, left = 0, right = 0;
while (right < N)
{
int cur_element = A[right];
repeat[cur_element] += 1;
// Increment counter
// if occurred once
if (repeat[cur_element] == 1)
++counter;
// When all unique
// elements are found
while (counter == count)
{
// Update answer with
// minimum size
ans = Math.Min(ans,
right - left + 1);
// Decrement count of
// elements from left
cur_element = A[left];
repeat[cur_element] -= 1;
++left;
// Decrement counter
if (repeat[cur_element] == 0)
--counter;
}
++right;
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
int N = 8, queries = 6;
int [,]Q = { { 1, 4 }, { 3, 4 }, { 4, 5 },
{ 5, 5 }, { 7, 8 }, { 8, 8 } };
int []A = new int[N];
Console.Write(subarrayLength(A, Q,
N, queries));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript implementation to find the
// minimum size subarray containing
// all unique elements after processing
// the array for K queries of ranges
// Function to find minimum size subarray
// of all array elements
function subarrayLength(A, R, N, M)
{
// Updating the array after
// processing each query
for (let i = 0; i < M; ++i)
{
let l = R[i][0], r = R[i][1] + 1;
// Making it to 0-indexing
l--;
r--;
// Prefix sum array concept is used
// to obtain the count array
A[l]++;
if (r < N)
A[r]--;
}
// Iterating over the array
// to get the final array
for (let i = 1; i < N; ++i)
{
A[i] += A[i - 1];
}
// Variable to get count
// of all unique elements
let count = 0;
// Hash to maintain previously
// occurred elements
let s = new Set();
// Loop to find the all
// unique elements
for (let i = 0; i < N; ++i)
{
if (!s.has(A[i]))
count++;
s.add(A[i]);
}
// array to maintain counter
// of encountered elements
let repeat = Array.from({length: count + 1}, (_, i) => 0);
// variable to store answer
let ans = N;
// Using two pointers approach
let counter = 0, left = 0, right = 0;
while (right < N)
{
let cur_element = A[right];
repeat[cur_element] += 1;
// Increment counter
// if occurred once
if (repeat[cur_element] == 1)
++counter;
// when all unique
// elements are found
while (counter == count)
{
// update answer with
// minimum size
ans = Math.min(ans,
right - left + 1);
// decrement count of
// elements from left
cur_element = A[left];
repeat[cur_element] -= 1;
++left;
// decrement counter
if (repeat[cur_element] == 0)
--counter;
}
++right;
}
return ans;
}
// Driver code
let N = 8, queries = 6;
let Q = [[ 1, 4 ], [ 3, 4 ], [ 4, 5 ],
[ 5, 5 ], [ 7, 8 ], [ 8, 8 ]];
let A = Array.from({length: N}, (_, i) => 0);
document.write(subarrayLength(A, Q,
N, queries));
</script>
Producción:
4
Complejidad de tiempo: O(N)
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA