Largest Non-Repeating Element

0 0 8 minutes read

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 i^th 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 array
void 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 Code
int 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 approach
 
import 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 approach
import sys
 
# Function to find the largest unique
# element of the array
def 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 Code
if __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 array
function 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 Code
var arr = [3, 1, 8, 8, 4 ];
var N = arr.length;
LarUnEl(arr, N);
 
 
 
</script>

Output

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 code
int 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 code
arr = [3, 1, 8, 8, 4]
N = len(arr)
print(largest(arr, N))

C#

// C# implementation program
using 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 equivalent
function 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 code
let arr = [3, 1, 8, 8, 4];
let N = arr.length;
console.log(largest(arr, N));

Output

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 zambiatek!