Given an array arr[] of size N, the task is to find the largest non-repeating element present in the given array. If no such element exists, then print -1.
Examples:
Input: arr[] = { 3, 1, 8, 8, 4 }
Output: 4
Explanation:
Non-repeating elements of the given array are { 1, 3, 4 }
Therefore, the largest non-repeating element of the given array is 4.Input: arr[] = { 3, 1, 8, 8, 3 }
Output: 1
Explanation:
Non-repeating elements of the given array are { 1 }
Therefore, the largest non-repeating element of the given array is 1.
Approach: The problem can be solved using Hashing. Follow the steps below to solve the problem:
- Initialize a Map, say mp, to store the frequency of each distinct element of the array.
- Traverse the array and store the frequencies of each array element.
- Initialize a variable, say LNRElem to store the largest non-repeating element present in the array.
- Traverse the array and for every ith element, check if frequency of arr[i] in the array is equal to 1 or not. If found to be true, then update LNRElem = max(LNRElem, arr[i]).
- Finally, print the value of LNRElem.
Below is implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the largest unique// element of the arrayvoid LarUnEl(int arr[], int N){ // Store frequency of each // distinct array element unordered_map<int, int> mp; // Traverse the array for (int i = 0; i < N; i++) { // Update frequency of arr[i] mp[arr[i]]++; } // Stores largest non-repeating // element present in the array int LNRElem = INT_MIN; // Stores index of the largest // unique element of the array int ind = -1; // Traverse the array for (int i = 0; i < N; i++) { // If frequency of arr[i] is equal // to 1 and arr[i] exceeds LNRElem if (mp[arr[i]] == 1 && arr[i] > LNRElem) { // Update ind ind = i; // Update LNRElem LNRElem = arr[i]; } } // If no array element is found // with frequency equal to 1 if (ind == -1) { cout << ind; return; } // Print the largest // non-repeating element cout << arr[ind];}// Driver Codeint main(){ int arr[] = { 3, 1, 8, 8, 4 }; int N = sizeof(arr) / sizeof(arr[0]); LarUnEl(arr, N);} |
Java
// Java program to implement// the above approachimport java.io.*;import java.util.*;class GFG { // Function to find the largest unique // element of the array static void LarUnEl(int arr[], int N) { // Store frequency of each distinct // element of the array HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); // Traverse the array for (int i = 0; i < N; i++) { // Update frequency of arr[i] map.put(arr[i], map.getOrDefault(arr[i], 0) + 1); } // Stores largest non-repeating // element present in the array int LNRElem = Integer.MIN_VALUE; // Stores index of the largest // non-repeating array element int ind = -1; // Traverse the array for (int i = 0; i < N; i++) { // If frequency of arr[i] is equal // to 1 and arr[i] exceeds LNRElem if (map.get(arr[i]) == 1 && arr[i] > LNRElem) { // Update ind ind = i; // Update LNRElem LNRElem = arr[i]; } } // If no array element is found // with frequency equal to 1 if (ind == -1) { System.out.println(ind); return; } // Print largest non-repeating element System.out.println(arr[ind]); } // Driver Code public static void main(String[] args) { int[] arr = { 3, 1, 8, 8, 4 }; int N = arr.length; LarUnEl(arr, N); }} |
Python3
# Python program to implement# the above approachimport sys# Function to find the largest unique# element of the arraydef LarUnEl(arr, N): # Store frequency of each distinct # element of the array map = dict.fromkeys(arr, 0); # Traverse the array for i in range(N): # Update frequency of arr[i] map[arr[i]] += 1; # Stores largest non-repeating # element present in the array LNRElem = -sys.maxsize; # Stores index of the largest # non-repeating array element ind = -1; # Traverse the array for i in range(N): # If frequency of arr[i] is equal # to 1 and arr[i] exceeds LNRElem if (map.get(arr[i]) == 1 and arr[i] > LNRElem): # Update ind ind = i; # Update LNRElem LNRElem = arr[i]; # If no array element is found # with frequency equal to 1 if (ind == -1): print(ind); return; # Print largest non-repeating element print(arr[ind]);# Driver Codeif __name__ == '__main__': arr = [3, 1, 8, 8, 4]; N = len(arr); LarUnEl(arr, N); # This code is contributed by shikhasingrajput |
C#
// C# program to implement// the above approach using System;using System.Collections.Generic;class GFG { // Function to find the largest unique // element of the array static void LarUnEl(int[] arr, int N) { // Store frequency of each distinct // element of the array Dictionary<int, int> map = new Dictionary<int, int>(); // Traverse the array for (int i = 0; i < N; i++) { // Update frequency of arr[i] if (map.ContainsKey(arr[i]) == true) map[arr[i]] += 1; else map[arr[i]] = 1; } // Stores largest non-repeating // element present in the array int LNRElem = Int32.MinValue; // Stores index of the largest // non-repeating array element int ind = -1; // Traverse the array for (int i = 0; i < N; i++) { // If frequency of arr[i] is equal // to 1 and arr[i] exceeds LNRElem if (map[arr[i]] == 1 && arr[i] > LNRElem) { // Update ind ind = i; // Update LNRElem LNRElem = arr[i]; } } // If no array element is found // with frequency equal to 1 if (ind == -1) { Console.WriteLine(ind); return; } // Print largest non-repeating element Console.WriteLine(arr[ind]); } // Drivers Code public static void Main () { int[] arr = { 3, 1, 8, 8, 4 }; int N = arr.Length; LarUnEl(arr, N); } }// This code is contributed by susmitakundugoaldanga |
Javascript
<script>// Javascript program to implement// the above approach// Function to find the largest unique// element of the arrayfunction LarUnEl(arr, N){ // Store frequency of each // distinct array element var mp = new Map(); // Traverse the array for (var i = 0; i < N; i++) { // Update frequency of arr[i] if(mp.has(arr[i])) mp.set(arr[i], mp.get(arr[i])+1) else mp.set(arr[i], 1); } // Stores largest non-repeating // element present in the array var LNRElem = -1000000000; // Stores index of the largest // unique element of the array var ind = -1; // Traverse the array for (var i = 0; i < N; i++) { // If frequency of arr[i] is equal // to 1 and arr[i] exceeds LNRElem if (mp.get(arr[i]) == 1 && arr[i] > LNRElem) { // Update ind ind = i; // Update LNRElem LNRElem = arr[i]; } } // If no array element is found // with frequency equal to 1 if (ind == -1) { cout << ind; return; } // Print the largest // non-repeating element document.write( arr[ind]);}// Driver Codevar arr = [3, 1, 8, 8, 4 ];var N = arr.length;LarUnEl(arr, N);</script> |
Output
4
Time complexity: O(N)
Auxiliary Space: O(N)
Another Approach: Using Sorting and O(1) extra space
- sort the given array
- traverse the array from the back and for each element check if it is equal to its previous element and also its next element
- for the next element, we use a variable named temp and for the previous element check, we simply use a[i]!=a[i-1].
- if the element is not equal that element is the answer otherwise continue the traversal
- once the traversal is over and if no element is found then return -1
Below is the implementation for the same:
C++
#include <bits/stdc++.h>using namespace std;int Largest(int a[], int n){ sort(a, a + n); // sorting the array int temp = a[n - 1]; // a variable used for comparing the last element to the // second last element to do the next element check for (int i = n - 2; i >= 0; i--) { // checking for suitable element if (temp != a[i]) { if (i == 0) return a[0]; if (i - 1 >= 0) { // checking if the element is non repeating if (a[i] != a[i - 1]) return a[i]; } // updating the right check temp = a[i]; } } // returning -1 if all elements are repeating elements return -1;}// driver codeint main(){ int arr[] = { 3, 1, 8, 8, 4 }; int N = sizeof(arr) / sizeof(arr[0]); cout << Largest(arr, N);} |
Java
import java.util.Arrays;public class Main { public static int largest(int[] a, int n) { Arrays.sort(a); // sorting the array int temp = a[n - 1]; // a variable used for comparing the last element to the second last element to do the next element check for (int i = n - 2; i >= 0; i--) { // checking for suitable element if (temp != a[i]) { if (i == 0) return a[0]; if (i - 1 >= 0) { // checking if the element is non repeating if (a[i] != a[i - 1]) return a[i]; } // updating the right check temp = a[i]; } } // returning -1 if all elements are repeating elements return -1; } // Driver code public static void main(String[] args) { int[] arr = { 3, 1, 8, 8, 4 }; int n = arr.length; System.out.println(largest(arr, n)); }} |
Python3
def largest(a, n): # sorting the array a.sort() # a variable used for comparing the last element to the # second last element to do the next element check temp = a[n - 1] # checking for suitable element for i in range(n - 2, -1, -1): if temp != a[i]: if i == 0: return a[0] if i - 1 >= 0: # checking if the element is non repeating if a[i] != a[i - 1]: return a[i] # updating the right check temp = a[i] # returning -1 if all elements are repeating elements return -1# driver codearr = [3, 1, 8, 8, 4]N = len(arr)print(largest(arr, N)) |
C#
// C# implementation programusing System;class Program{ static int Largest(int[] a, int n) { // sorting the array Array.Sort(a); int temp = a[n - 1]; for (int i = n - 2; i >= 0; i--) { // checking for suitable element if (temp != a[i]) { if (i == 0) return a[0]; if (i - 1 >= 0) { // checking if the element is non repeating if (a[i] != a[i - 1]) return a[i]; } // updating the right value temp = a[i]; } } // if all of the components are repeated ones, returning -1 return -1; } // drive code static void Main(string[] args) { int[] arr = { 3, 1, 8, 8, 4 }; int N = arr.Length; Console.WriteLine(Largest(arr, N)); }} |
Javascript
// js equivalentfunction largest(a, n) { // sorting the array a.sort(); // a variable used for comparing the last element to the // second last element to do the next element check let temp = a[n - 1]; // checking for suitable element for (let i = n - 2; i >= 0; i--) { if (temp != a[i]) { if (i == 0) return a[0]; if (i - 1 >= 0) { // checking if the element is non repeating if (a[i] != a[i - 1]) { return a[i]; } } // updating the right check temp = a[i]; } } // returning -1 if all elements are repeating elements return -1;}// driver codelet arr = [3, 1, 8, 8, 4];let N = arr.length;console.log(largest(arr, N)); |
Output
4
Time Complexity: O(NlogN) Since we are using sorting
Auxiliary Space: O(1) No Extra space is used.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
