Dada una array , arr[] que representa una permutación de los primeros N números naturales en el rango [1, N] , la tarea para cada i -ésimo índice es comprobar si existe o no un subarreglo de i-longitud que contenga todos los números en el rango [1, i] .
Nota: 1: indexación basada en uso.
Ejemplos:
Entrada: arr[] = {4, 5, 1, 3, 2}
Salida : Verdadero Falso Verdadero Falso Verdadero
Explicación :
Para i = 1, el subarreglo {arr[2]} contiene todos los números de [1, i] y de tamaño i(=1). Por lo tanto, la salida requerida es verdadera.
Para i = 2, no existe ningún subarreglo de tamaño 2 que contenga todos los números en el rango [1, i]. Por lo tanto, la salida requerida es falsa.
Para i = 3, el subarreglo {arr[2], arr[3], arr[4]} contiene todos los números de [1, i] y de tamaño i(=3). Por lo tanto, la salida requerida es verdadera.
Para i = 4, no existe ningún subarreglo de tamaño 4 que contenga todos los números en el rango [1, i]. Por lo tanto, la salida requerida es falsa.
Para i = 5, el subarreglo {arr[0], arr[1], arr[2], arr[3], arr[4]} contiene todos los números de [1, i] y de tamaño i(=5 ). Por lo tanto, la salida requerida es verdadera.Entrada: arr = {1, 4, 3, 2}
Salida: Verdadero Falso Falso Verdadero
Enfoque ingenuo: la idea es recorrer la array y, para cada índice, verificar si hay una subarreglo de tamaño i que contiene todos los números en el rango [1, i] o no. Si se encuentra que es verdadero, imprima Verdadero . De lo contrario, escriba Falso.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: el problema se puede resolver utilizando Hashing para almacenar la posición de cada elemento de la array dada de manera eficiente. Siga los pasos a continuación para resolver el problema:
- Cree un mapa , digamos, Mapa , para almacenar la posición de cada elemento de la array dada.
- Atraviese la array y almacene la posición de cada elemento de la array en Map .
- Cree un conjunto , digamos st para almacenar los índices de cada elemento del rango [1, N] .
- Inicialice dos variables, digamos Min y Max , para almacenar los elementos más pequeños y más grandes presentes en st .
- Itere sobre el rango [1, N] e inserte el valor de Map[i] en st y verifique si Max – Min + 1 = i o no. Si se encuentra que es verdadero, imprima Verdadero .
- De lo contrario, imprime Falso .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if a subarray of size i exists
// that contain all the numbers in the range [1, i]
void checksubarrayExist1_N(int arr[], int N)
{
// Store the position
// of each element of arr[]
unordered_map<int, int> pos;
// Traverse the array
for (int i = 0; i < N; i++) {
// Insert the position
// of arr[i]
pos[arr[i]] = i;
}
// Store position of each element
// from the range [1, N]
set<int> st;
// Iterate over the range [1, N]
for (int i = 1; i <= N; i++) {
// Insert the index of i into st
st.insert(pos[i]);
// Find the smallest element of st
int Min = *(st.begin());
// Find the largest element of st
int Max = *(st.rbegin());
// If distance between the largest
// and smallest element of arr[]
// till i-th index is equal to i
if (Max - Min + 1 == i) {
cout << "True ";
}
else {
cout << "False ";
}
}
}
// Driver Code
int main()
{
int arr[] = { 1, 4, 3, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
checksubarrayExist1_N(arr, N);
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG {
// Function to check if a subarray of size i exists
// that contain all the numbers in the range [1, i]
static void checksubarrayExist1_N(int arr[], int N)
{
// Store the position
// of each element of arr[]
Map<Integer, Integer> pos=new HashMap<>();
// Traverse the array
for (int i = 0; i < N; i++) {
// Insert the position
// of arr[i]
pos.put(arr[i],i);
}
// Store position of each element
// from the range [1, N]
Set<Integer> st=new HashSet<>();
// Iterate over the range [1, N]
for (int i = 1; i <= N; i++) {
// Insert the index of i into st
st.add(pos.get(i));
// Find the smallest element of st
int Min = Collections.min(st);
// Find the largest element of st
int Max = Collections.max(st);
// If distance between the largest
// and smallest element of arr[]
// till i-th index is equal to i
if (Max - Min + 1 == i) {
System.out.print("True ");
}
else {
System.out.print("False ");
}
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 4, 3, 2 };
int N = arr.length;
checksubarrayExist1_N(arr, N);
}
}
// This code is contributed by offbeat
Python3
# Python3 program to implement
# the above approach
# Function to check if a subarray of size i exists
# that contain all the numbers in the range [1, i]
def checksubarrayExist1_N(arr, N):
# Store the position
# of each element of arr[]
pos = {}
# Traverse the array
for i in range(N):
# Insert the position
# of arr[i]
pos[arr[i]] = i
# Store position of each element
# from the range [1, N]
st = {}
# Iterate over the range [1, N]
for i in range(1, N + 1):
# Insert the index of i into st
st[pos[i]] = 1
# Find the smallest element of st
Min = sorted(list(st.keys()))[0]
# Find the largest element of st
Max = sorted(list(st.keys()))[-1]
# If distance between the largest
# and smallest element of arr[]
# till i-th index is equal to i
if (Max - Min + 1 == i):
print("True", end = " ")
else:
print("False", end = " ")
# Driver Code
if __name__ == '__main__':
arr = [1, 4, 3, 2]
N = len(arr)
checksubarrayExist1_N(arr, N)
# This code is contributed by mohit kumar 29.
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
using System.Linq;
class GFG{
// Function to check if a subarray of size i exists
// that contain all the numbers in the range [1, i]
static void checksubarrayExist1_N(int[] arr, int N)
{
// Store the position
// of each element of arr[]
Dictionary<int,
int> pos = new Dictionary<int,
int>();
// Traverse the array
for(int i = 0; i < N; i++)
{
// Insert the position
// of arr[i]
pos[arr[i]] = i;
}
// Store position of each element
// from the range [1, N]
HashSet<int> st = new HashSet<int>();
// Iterate over the range [1, N]
for(int i = 1; i <= N; i++)
{
// Insert the index of i into st
st.Add(pos[i]);
// Find the smallest element of st
int Min = st.Min();
// Find the largest element of st
int Max = st.Max();
// If distance between the largest
// and smallest element of arr[]
// till i-th index is equal to i
if (Max - Min + 1 == i)
{
Console.Write("True ");
}
else
{
Console.Write("False ");
}
}
}
// Driver code
public static void Main(string[] args)
{
int[] arr = { 1, 4, 3, 2 };
int N = arr.Length;
checksubarrayExist1_N(arr, N);
}
}
// This code is contributed by ukasp
Javascript
<script>
// JavaScript program for the above approach
// Function to check if a subarray of size i exists
// that contain all the numbers in the range [1, i]
function checksubarrayExist1_N(arr, N)
{
// Store the position
// of each element of arr[]
let pos = new Map();
// Traverse the array
for (let i = 0; i < N; i++) {
// Insert the position
// of arr[i]
pos.set(arr[i],i);
}
// Store position of each element
// from the range [1, N]
let st=new Set();
// Iterate over the range [1, N]
for (let i = 1; i <= N; i++) {
// Insert the index of i into st
st.add(pos.get(i));
// Find the smallest element of st
let Min = Math.min(...st);
// Find the largest element of st
let Max = Math.max(...st);
// If distance between the largest
// and smallest element of arr[]
// till i-th index is equal to i
if (Max - Min + 1 == i) {
document.write("True ");
}
else {
document.write("False ");
}
}
}
// Driver Code
let arr = [ 1, 4, 3, 2 ];
let N = arr.length;
checksubarrayExist1_N(arr, N);
</script>
True False False True
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por aqibmahboob1999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA