Dada una array arr[] de longitud N y entero K , la tarea es imprimir rangos de subarreglo (índice inicial, índice final) del arreglo donde la diferencia entre los elementos máximo y mínimo del subarreglo es exactamente K. (índice basado en 1)
Ejemplos:
Entrada: arr[] = {2, 1, 3, 4, 2, 6}, K = 2
Salida: (1, 3), (2, 3), (3, 5), (4, 5)
Explicación: En la array anterior, los siguientes rangos de la array secundaria tienen una diferencia máxima mínima exactamente K
(1, 3) => máx = 3 y mín = 1. Diferencia = 3 – 1 = 2
(2, 3) => máx = 3 y mín = 1 Diferencia = 3 – 1 = 2
(3, 5) => max = 4 y min = 2. Diferencia = 4 – 2 = 2
(4, 5) => max = 4 y min = 2. Diferencia = 4 – 2 = 2Entrada: arr[] = {5, 3, 4, 6, 1, 2}, K = 6
Salida: -1
Explicación: No existen tales rangos de subarray.
Enfoque: La idea básica para resolver el problema es formar todos los subarreglos y encontrar el mínimo y el máximo y su diferencia para cada subarreglo. Siga los pasos que se mencionan a continuación para resolver el problema.
- Iterar sobre la array de i = 0 a N-1 :
- Iterar de j = i a N-1 :
- Inserte el elemento actual arr[j] en un conjunto que almacena el subarreglo actual a partir de i .
- Encuentre el mínimo y el máximo del conjunto.
- Obtenga su diferencia y verifique si su diferencia es igual a K o no.
- Si es así, empuje este rango en la respuesta.
- Iterar de j = i a N-1 :
- Devuelve los rangos.
- Si no hay tal rango, devuelva -1.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print index ranges
void printRanges(vector<int> arr, int n,
int K)
{
int i, j, f = 0;
for (i = 0; i < n; i++) {
// Set to store the elements
// of a subarray
set<int> s;
for (j = i; j < n; j++) {
// Insert current element in set
s.insert(arr[j]);
// Calculate max and min for
// any particular index range
int max = *s.rbegin();
int min = *s.begin();
// If we get max-min = K
// print 1 based index
if (max - min == K) {
cout << i + 1 << " " << j + 1
<< "\n";
f = 1;
}
}
}
// If we didn't find any index ranges
if (f == 0)
cout << -1 << endl;
}
// Driver Code
int main()
{
vector<int> arr = { 2, 1, 3, 4, 2, 6 };
int N = arr.size();
int K = 2;
// Function call
printRanges(arr, N, K);
return 0;
}
Java
// Java implementation of above approach
import java.util.*;
class GFG {
// Function to print index ranges
static void printRanges(int arr[], int n,
int K)
{
int i, j, f = 0;
for (i = 0; i < n; i++) {
// Set to store the elements
// of a subarray
Set<Integer> s = new HashSet<>();
for (j = i; j < n; j++) {
// Insert current element in set
s.add(arr[j]);
// Calculate max and min for
// any particular index range
int max = Collections.max(s);
int min = Collections.min(s);
// If we get max-min = K
// print 1 based index
if (max - min == K) {
System.out.println( (i + 1) + " " + (j + 1));
f = 1;
}
}
}
// If we didn't find any index ranges
if (f == 0)
System.out.println(-1);
}
// Driver Code
public static void main (String[] args) {
int arr[] = { 2, 1, 3, 4, 2, 6 };
int N = arr.length;
int K = 2;
// Function call
printRanges(arr, N, K);
}
}
// This code is contributed by hrithikgarg03188.
Python3
# python3 implementation of above approach
# Function to print index ranges
def printRanges(arr, n, K):
i, j, f = 0, 0, 0
for i in range(0, n):
# Set to store the elements
# of a subarray
s = set()
for j in range(i, n):
# Insert current element in set
s.add(arr[j])
# Calculate max and min for
# any particular index range
ma = max(list(s))
mi = min(list(s))
# If we get max-min = K
# print 1 based index
if (ma - mi == K):
print(f"{i + 1} {j + 1}")
f = 1
# If we didn't find any index ranges
if (f == 0):
print(-1)
# Driver Code
if __name__ == "__main__":
arr = [2, 1, 3, 4, 2, 6]
N = len(arr)
K = 2
# Function call
printRanges(arr, N, K)
# This code is contributed by rakeshsahni
C#
// C# implementation of above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to print index ranges
static void printRanges(int[] arr, int n, int K)
{
int i, j, f = 0;
for (i = 0; i < n; i++) {
// Set to store the elements
// of a subarray
HashSet<int> s = new HashSet<int>();
for (j = i; j < n; j++) {
// Insert current element in set
s.Add(arr[j]);
// Calculate max and min for
// any particular index range
int max = int.MinValue,min = int.MaxValue;
foreach(var value in s)
{
max = Math.Max(max,value);
min = Math.Min(min,value);
}
// If we get max-min = K
// print 1 based index
if (max - min == K) {
Console.Write( (i + 1) + " " + (j + 1) + "\n");
f = 1;
}
}
}
// If we didn't find any index ranges
if (f == 0)
Console.Write(-1);
}
// Driver Code
public static void Main()
{
int[] arr = { 2, 1, 3, 4, 2, 6 };
int N = arr.Length;
int K = 2;
// Function call
printRanges(arr, N, K);
}
}
// This code is contributed by aditya942003patil.
Javascript
<script>
// Javascript implementation of above approach
// Function to print index ranges
function printRanges(arr, n, K)
{
let i = 0, j = 0, f = 0;
for (i = 0; i < n; i++) {
// Set to store the elements
// of a subarray
const s = new Set();
for (j = i; j < n; j++) {
// Insert current element in set
s.add(arr[j]);
// Calculate max and min for
// any particular index range
let max = Math.max(...s);
let min = Math.min(...s);
// If we get max-min = K
// print 1 based index
if (max - min == K) {
document.write((i+1) + " " + (j+1) + "<br>");
f = 1;
}
}
}
// If we didn't find any index ranges
if (f == 0)
document.write(-1);
}
// Driver Code
let arr = [ 2, 1, 3, 4, 2, 6 ];
let N = arr.length;
let K = 2;
// Function call
printRanges(arr, N, K);
// This code is contributed by aditya942003patil.
</script>
Producción
1 3 2 3 3 5 4 5
Complejidad de Tiempo: O(N 2 * logN)
Espacio Auxiliar: O(N)
Enfoque eficiente: en lugar de usar HashSet, realice un seguimiento del elemento máximo y mínimo actual mientras recorre la array.
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print index ranges
void printRanges(vector<int> arr, int n, int K)
{
int i = 0, j = 0, f = 0;
for (i = 0; i < n; i++) {
int mx = INT_MIN, mn = INT_MAX;
for (j = i; j < n; j++) {
// Calculate max and min for
// any particular index range
mx = max(mx, arr[j]);
mn = min(mn, arr[j]);
// If we get max-min = K
// print 1 based index
if (mx - mn == K) {
cout << (i + 1) << " " << (j + 1) << endl;
f = 1;
}
}
}
// If we didn't find any index ranges
if (f == 0)
cout << -1;
}
// Driver Code
int main()
{
vector<int> arr = { 2, 1, 3, 4, 2, 6 };
int N = arr.size();
int K = 2;
// Function call
printRanges(arr, N, K);
}
// This code is contributed by Samim Hossain Mondal.
Java
// Java implementation of above approach
import java.util.*;
public class GFG {
// Function to print index ranges
static void printRanges(int[] arr, int n, int K)
{
int i = 0, j = 0, f = 0;
for (i = 0; i < n; i++) {
int mx = Integer.MIN_VALUE, mn
= Integer.MAX_VALUE;
for (j = i; j < n; j++) {
// Calculate max and min for
// any particular index range
mx = Math.max(mx, arr[j]);
mn = Math.min(mn, arr[j]);
// If we get max-min = K
// print 1 based index
if (mx - mn == K) {
System.out.println((i + 1) + " "
+ (j + 1));
f = 1;
}
}
}
// If we didn't find any index ranges
if (f == 0)
System.out.print(-1);
}
// Driver Code
public static void main(String args[])
{
int[] arr = { 2, 1, 3, 4, 2, 6 };
int N = arr.length;
int K = 2;
// Function call
printRanges(arr, N, K);
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python3 implementation of above approach
# import the module
import sys
# Function to print index ranges
def printRanges(arr, n, K):
i, j, f = 0, 0, 0
for i in range(0, n):
mn = sys.maxsize
mx = -1*sys.maxsize
for j in range(i, n):
# Calculate max and min for
# any particular index range
mx = max(mx, arr[j])
mn = min(mn, arr[j])
# If we get max-min=K
# print 1 based index
if(mx - mn == K):
print(f"{i + 1} {j + 1}")
f=1
# If we didn't find any index ranges
if (f == 0):
print(-1)
# Driver Code
if __name__ == "__main__":
arr = [2, 1, 3, 4, 2, 6]
N = len(arr)
K = 2
# Function call
printRanges(arr, N, K)
# This code is contributed by Pushpesh Raj
C#
// C# implementation of above approach
using System;
class GFG {
// Function to print index ranges
static void printRanges(int[] arr, int n, int K)
{
int i = 0, j = 0, f = 0;
for (i = 0; i < n; i++) {
int mx = Int32.MinValue, mn = Int32.MaxValue;
for (j = i; j < n; j++) {
// Calculate max and min for
// any particular index range
mx = Math.Max(mx, arr[j]);
mn = Math.Min(mn, arr[j]);
// If we get max-min = K
// print 1 based index
if (mx - mn == K) {
Console.WriteLine((i + 1) + " "
+ (j + 1));
f = 1;
}
}
}
// If we didn't find any index ranges
if (f == 0)
Console.Write(-1);
}
// Driver Code
public static void Main()
{
int[] arr = { 2, 1, 3, 4, 2, 6 };
int N = arr.Length;
int K = 2;
// Function call
printRanges(arr, N, K);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript implementation of above approach
// Function to print index ranges
function printRanges(arr, n, K)
{
let i = 0, j = 0, f = 0;
for (i = 0; i < n; i++) {
let mx = Number.MIN_SAFE_INTEGER, mn = Number.MAX_SAFE_INTEGER;
for (j = i; j < n; j++) {
// Calculate max and min for
// any particular index range
mx = Math.max(mx, arr[j]);
mn = Math.min(mn, arr[j]);
// If we get max-min = K
// print 1 based index
if (mx - mn == K) {
document.write((i + 1) + " " + (j + 1));
f = 1;
}
}
}
// If we didn't find any index ranges
if (f == 0)
document.write(-1);
}
// Driver Code
let arr = [ 2, 1, 3, 4, 2, 6 ];
let N = arr.length;
let K = 2;
// Function call
printRanges(arr, N, K);
// This code is contributed by Samim Hossain Mondal.
</script>
Producción
1 3 2 3 3 5 4 5
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)