Dado un arreglo circular arr[] de N enteros tal que el último elemento del arreglo dado es adyacente al primer elemento del arreglo, la tarea es imprimir el Próximo Elemento Mayor en este arreglo circular. Elementos para los que no existe un elemento mayor, considere el siguiente elemento mayor como «-1» .
Ejemplos:
Entrada: arr[] = {5, 6, 7}
Salida: {6, 7, -1}
Explicación:
El siguiente elemento mayor para 5 es 6, para 6 es 7 y para 7 es -1 ya que no tenemos cualquier elemento mayor que sí mismo por lo que es -1.Entrada: arr[] = {4, -2, 5, 8}
Salida: {5, 5, 8, -1}
Explicación:
El siguiente elemento mayor para 4 es 5, para -2 es 5, para 5 es 8 y para 8 es -1 ya que no tenemos ningún elemento mayor que él mismo entonces es -1, y para 3 es 4.
Enfoque: este problema se puede resolver utilizando el enfoque codicioso . A continuación se muestran los pasos:
- Para que la propiedad de la array circular sea válida, agregue los elementos de array dados a la misma array una vez más.
Por ejemplo:
Sea arr[] = {1, 4, 3}
Después de agregar el mismo conjunto de elementos, arr[] se convierte en
arr[] = {1, 4, 3, 1, 4, 3}
- Encuentre el siguiente elemento mayor hasta que se formen N elementos en la array anterior.
- Si se encuentra algún elemento mayor, imprima ese elemento, de lo contrario, imprima «-1» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the NGE
void printNGE(int A[], int n)
{
// Formation of circular array
int arr[2 * n];
// Append the given array element twice
for (int i = 0; i < 2 * n; i++)
arr[i] = A[i % n];
int next, i, j;
// Iterate for all the elements of the array
for (i = 0; i < n; i++) {
// Initialise NGE as -1
next = -1;
for (j = i + 1; j < 2 * n; j++) {
// Checking for next greater element
if (arr[i] < arr[j]) {
next = arr[j];
break;
}
}
// Print the updated NGE
cout << next << ", ";
}
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 2, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
printNGE(arr, N);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program for the above approach
#include <stdio.h>
// Function to find the NGE
void printNGE(int A[], int n)
{
// Formation of circular array
int arr[2 * n];
// Append the given array element twice
for (int i = 0; i < 2 * n; i++)
arr[i] = A[i % n];
int next, i, j;
// Iterate for all the elements of the array
for (i = 0; i < n; i++) {
// Initialise NGE as -1
next = -1;
for (j = i + 1; j < 2 * n; j++) {
// Checking for next greater element
if (arr[i] < arr[j]) {
next = arr[j];
break;
}
}
// Print the updated NGE
printf("%d, ",next);
}
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 2, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
printNGE(arr, N);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find the NGE
static void printNGE(int[] A, int n)
{
// Formation of circular array
int[] arr = new int[2 * n];
// Append the given array element twice
for (int i = 0; i < 2 * n; i++)
arr[i] = A[i % n];
int next;
// Iterate for all the elements of the array
for (int i = 0; i < n; i++) {
// Initialise NGE as -1
next = -1;
for (int j = i + 1; j < 2 * n; j++) {
// Checking for next greater element
if (arr[i] < arr[j]) {
next = arr[j];
break;
}
}
// Print the updated NGE
System.out.print(next + ", ");
}
}
// Driver Code
public static void main(String args[])
{
// Given array arr[]
int[] arr = { 1, 2, 1 };
int N = arr.length;
// Function call
printNGE(arr, N);
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Python3 program for the above approach # Function to find the NGE def printNGE(A, n): # Formation of circular array arr = [0] * (2 * n) # Append the given array # element twice for i in range(2 * n): arr[i] = A[i % n] # Iterate for all the # elements of the array for i in range(n): # Initialise NGE as -1 next = -1 for j in range(i + 1, 2 * n): # Checking for next # greater element if(arr[i] < arr[j]): next = arr[j] break # Print the updated NGE print(next, end = ", ") # Driver code if __name__ == '__main__': # Given array arr[] arr = [ 1, 2, 1 ] N = len(arr) # Function call printNGE(arr, N) # This code is contributed by Shivam Singh
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the NGE
static void printNGE(int []A, int n)
{
// Formation of circular array
int []arr = new int[2 * n];
// Append the given array element twice
for(int i = 0; i < 2 * n; i++)
arr[i] = A[i % n];
int next;
// Iterate for all the
// elements of the array
for(int i = 0; i < n; i++)
{
// Initialise NGE as -1
next = -1;
for(int j = i + 1; j < 2 * n; j++)
{
// Checking for next
// greater element
if (arr[i] < arr[j])
{
next = arr[j];
break;
}
}
// Print the updated NGE
Console.Write(next + ", ");
}
}
// Driver Code
public static void Main()
{
// Given array arr[]
int []arr = { 1, 2, 1 };
int N = arr.Length;
// Function call
printNGE(arr, N);
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// JavaScript program for the above approach
// Function to find the NGE
function printNGE(A, n)
{
// Formation of circular array
let arr = Array.from({length: 2 * n}, (_, i) => 0);
// Append the given array element twice
for(let i = 0; i < 2 * n; i++)
arr[i] = A[i % n];
let next;
// Iterate for all the
// elements of the array
for(let i = 0; i < n; i++)
{
// Initialise NGE as -1
next = -1;
for(let j = i + 1; j < 2 * n; j++)
{
// Checking for next
// greater element
if (arr[i] < arr[j])
{
next = arr[j];
break;
}
}
// Print the updated NGE
document.write(next + ", ");
}
}
// Driver Code
// Given array arr[]
let arr = [ 1, 2, 1 ];
let N = arr.length;
// Function call
printNGE(arr, N);
</script>
Producción
2, -1, 2,
Este enfoque toma tiempo O(n 2 ) pero toma espacio adicional de orden O(n)
Una solución eficiente en el espacio es tratar con arreglos circulares usando el mismo arreglo. Si se ejecuta una observación cuidadosa a través de la array, luego del índice n-ésimo, el siguiente índice siempre comienza desde 0, por lo que usando el operador mod , podemos acceder fácilmente a los elementos de la lista circular, si usamos (i)%n y ejecute el bucle desde el índice i-th hasta el índice n+i-th, y aplique mod. Podemos hacer el recorrido en una array circular dentro de la array dada sin usar ningún espacio adicional.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to demonstrate the use of circular
// array without using extra memory space
#include <bits/stdc++.h>
using namespace std;
// Function to find the Next Greater Element(NGE)
void printNGE(int A[], int n)
{
int k;
for(int i = 0; i < n; i++)
{
// Initialise k as -1 which is printed
// when no NGE found
k = -1;
for(int j = i + 1; j < n + i; j++)
{
if (A[i] < A[j % n])
{
cout <<" "<< A[j % n];
k = 1;
break;
}
}
// Gets executed when no NGE found
if (k == -1)
cout << "-1 ";
}
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 8, 6, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
printNGE(arr, N);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to demonstrate the use of circular
// array without using extra memory space
#include <stdio.h>
// Function to find the Next Greater Element(NGE)
void printNGE(int A[], int n)
{
int k;
for (int i = 0; i < n; i++) {
// Initialise k as -1 which is printed when no NGE
// found
k = -1; //
for (int j = i + 1; j < n + i; j++) {
if (A[i] < A[j % n]) {
printf("%d ", A[j % n]);
k = 1;
break;
}
}
if (k == -1) // Gets executed when no NGE found
printf("-1 ");
}
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 8, 6, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
printNGE(arr, N);
return 0;
}
Java
// Java program to demonstrate the use of circular array
// without using extra memory space
import java.io.*;
class GFG {
// Function to find the Next
// Greater Element(NGE)
static void printNGE(int A[], int n)
{
int k;
for (int i = 0; i < n; i++) {
// Initialise k as -1 which is printed when no
// NGE found
k = -1;
for (int j = i + 1; j < n + i; j++) {
if (A[i] < A[j % n]) {
System.out.print(A[j % n] + " ");
k = 1;
break;
}
}
// Gets executed when no NGE found
if (k == -1)
System.out.print("-1 ");
}
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int[] arr = { 8, 6, 7 };
int N = arr.length;
// Function call
printNGE(arr, N);
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Python3 program to demonstrate the use of circular
# array without using extra memory space
# Function to find the Next Greater Element(NGE)
def printNGE(A, n) :
for i in range(n) :
# Initialise k as -1 which is printed when no NGE
# found
k = -1
for j in range(i + 1, n + i) :
if (A[i] < A[j % n]) :
print(A[j % n], end = " ")
k = 1
break
if (k == -1) : # Gets executed when no NGE found
print("-1 ", end = "")
# Given array arr[]
arr = [ 8, 6, 7 ]
N = len(arr)
# Function call
printNGE(arr, N)
# This code is contributed by divyeshrabadia07
C#
// C# program to demonstrate the
// use of circular array without
// using extra memory space
using System;
class GFG {
// Function to find the Next
// Greater Element(NGE)
static void printNGE(int[] A, int n)
{
int k;
for(int i = 0; i < n; i++)
{
// Initialise k as -1 which is
// printed when no NGE found
k = -1;
for(int j = i + 1; j < n + i; j++)
{
if (A[i] < A[j % n])
{
Console.Write(A[j % n] + " ");
k = 1;
break;
}
}
// Gets executed when no NGE found
if (k == -1)
Console.Write("-1 ");
}
}
static void Main()
{
// Given array arr[]
int[] arr = { 8, 6, 7 };
int N = arr.Length;
// Function call
printNGE(arr, N);
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// JavaScript program to demonstrate the
// use of circular array without
// using extra memory space
// Function to find the Next
// Greater Element(NGE)
function printNGE(A, n)
{
let k;
for(let i = 0; i < n; i++)
{
// Initialise k as -1 which is
// printed when no NGE found
k = -1;
for(let j = i + 1; j < n + i; j++)
{
if (A[i] < A[j % n])
{
document.write(A[j % n] + " ");
k = 1;
break;
}
}
// Gets executed when no NGE found
if (k == -1)
document.write("-1 ");
}
}
// Given array arr[]
let arr = [ 8, 6, 7 ];
let N = arr.length;
// Function call
printNGE(arr, N);
</script>
Producción
-1 7 8
Tiempo Complejidad: O(n 2 )
Espacio Auxiliar: O(1)
Método 3: El método usa el mismo concepto usado en el método 2 para Array circular pero usa Stack para encontrar el siguiente elemento mayor en complejidad de tiempo O(n) donde n es el tamaño del arreglo. Para una mejor comprensión, puede ver el siguiente elemento mayor .
C++
#include <bits/stdc++.h>
using namespace std;
// Function to find the Next Greater Element(NGE)
void printNGE(int a[], int n)
{
stack<int> s;
vector<int> ans(n);
for (int i = 2 * n - 1; i >= 0; i--) {
while (!s.empty() && a[i % n] >= s.top())
s.pop();
if (i < n) {
if (!s.empty())
ans[i] = s.top();
else
ans[i] = -1;
}
s.push(a[i % n]);
}
for (int i = 0; i < n; i++)
cout << ans[i] << " ";
}
// Driver Code
int main()
{
int arr[] = { 8, 6, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
printNGE(arr, N);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG {
public static void printNGE(int[] arr)
{
Stack<Integer> stack = new Stack<>();
int n = arr.length;
int[] result = new int[n];
for(int i = 2*n - 1; i >= 0; i--)
{
// Remove all the elements in Stack that are less than arr[i%n]
while(!stack.isEmpty() && arr[i % n] >= stack.peek()){
stack.pop();
}
if(i < n)
{
if(!stack.isEmpty())
result[i] = stack.peek();
else
result[i] = -1; // When none of elements in Stack are greater than arr[i%n]
}
stack.push(arr[i % n]);
}
for(int i:result)
{
System.out.print(i + " ");
}
}
// Driver code
public static void main (String[] args) {
int[] arr = {8, 6 , 7};
printNGE(arr);
}
}
// This code is contributed by vaibhavpatel1904.
Python3
# Function to find the Next Greater Element(NGE) def printNGE(a, n): s = [] ans = [0] * n for i in range(2 * n - 1, -1, -1): while s and a[i % n] >= s[-1]: s.pop() if i < n: if s: ans[i] = s[-1] else: ans[i] = -1 s.append(a[i % n]) for i in range(n): print(ans[i], end=" ") # Driver Code if __name__ == "__main__": # Given array arr[] arr = [8, 6, 7] N = len(arr) # Function call printNGE(arr, N)
Javascript
<script>
// Function to find the Next Greater Element(NGE)
function printNGE(a, n){
let s = []
let ans = new Array(n).fill(0)
for(let i=2 * n - 1;i>=0;i--){
while(s.length>0 && a[i % n] >= s[s.length - 1])
s.pop()
if(i < n){
if(s.length>0)
ans[i] = s[s.length-1]
else
ans[i] = -1
}
s.push(a[i % n])
}
for(let i=0;i<n;i++){
document.write(ans[i]," ")
}
}
// Driver Code
// Given array arr[]
let arr = [8, 6, 7]
let N = arr.length
// Function call
printNGE(arr, N)
// code is contributed by shinjanpatra
</script>
Producción
-1 7 8
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Método: – 4
En el método 3, el siguiente elemento mayor se calcula recorriendo la array desde atrás (final), pero también podemos hacer lo mismo en el recorrido hacia adelante (inicio).
C++
// C++ code to find the next greater element
// in circular array.
#include <bits/stdc++.h>
using namespace std;
// Function to find the Next Greater Element(NGE)
void printNGE(int nums[], int n)
{
// Stores the next greater element for index i.
vector<int> ans(n, -1);
stack<int> s;
for (int i = 0; i < 2 * n; i++) {
while (!s.empty() && nums[s.top()] < nums[i % n]) {
ans[s.top()] = nums[i % n];
s.pop();
}
if (i < n)
s.push(i);
}
for (auto it : ans)
cout << it << " ";
}
// Driver Code
int main()
{
int arr[] = { 8, 6, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
printNGE(arr, N);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Javascript
<script>
// JavaScript code to find the next greater element
// in circular array.
// Function to find the Next Greater Element(NGE)
function printNGE(nums, n)
{
// Stores the next greater element for index i.
let ans = new Array(n).fill(-1);
let s = [];
for (let i = 0; i < 2 * n; i++) {
while (s.length > 0 && nums[s[s.length - 1]] < nums[i % n]) {
ans[s[s.length - 1]] = nums[i % n];
s.pop();
}
if (i < n)
s.push(i);
}
for (let it of ans)
document.write(it , " ");
}
// Driver Code
let arr = [ 8, 6, 7 ];
let N = arr.length;
printNGE(arr, N);
// This code is contributed by shinjanpatra
</script>
Producción
-1 7 8
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Shivamthakur77 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA