Given an array of N elements, print the elements in the same relative order as given by removing all the occurrences of elements except the last occurrence.
Examples:
Input: a[] = {1, 5, 5, 1, 6, 1}
Output: 5 6 1
Remove two integers 1, which are in the positions 1 and 4. Also, remove the integer 5, which is in the position 2.
Hence the left array is {5, 6, 1}Input: a[] = {2, 5, 5, 2}
Output: 5 2
Approach:
- Hash the last occurrence of every element.
- Iterate in the array of N elements, if the element’s index is hashed, then print the array element.
Below is the implementation of the above approach:
C++
// C++ program to print the last occurrence// of every element in relative order#include <bits/stdc++.h>using namespace std;// Function to print the last occurrence// of every element in an arrayvoid printLastOccurrence(int a[], int n){ // used in hashing unordered_map<int, int> mp; // iterate and store the last index // of every element for (int i = 0; i < n; i++) mp[a[i]] = i; // iterate and check for the last // occurrence of every element for (int i = 0; i < n; i++) { if (mp[a[i]] == i) cout << a[i] << " "; }}// Driver Codeint main(){ int a[] = { 1, 5, 5, 1, 6, 1 }; int n = sizeof(a) / sizeof(a[0]); printLastOccurrence(a, n); return 0;} |
Java
// Java program to print the // last occurrence of every // element in relative orderimport java.util.*;class GFG{ // Function to print the last // occurrence of every element // in an array public static void printLastOccurrence(int a[], int n) { HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); // iterate and store the last // index of every element for (int i = 0; i < n; i++) map.put(a[i], i); for (int i = 0; i < n; i++) { if (map.get(a[i]) == i) System.out.print(a[i] +" "); } } // Driver Code public static void main (String[] args) { int a[] = { 1, 5, 5, 1, 6, 1 }; int n = a.length; printLastOccurrence(a, n); }}// This code is contributed// by ankita_saini |
Python3
# Python 3 program to print the last occurrence# of every element in relative order# Function to print the last occurrence# of every element in an arraydef printLastOccurrence(a, n): # used in hashing mp = {i:0 for i in range(7)} # iterate and store the last # index of every element for i in range(n): mp[a[i]] = i # iterate and check for the last # occurrence of every element for i in range(n): if (mp[a[i]] == i): print(a[i], end = " ")# Driver Codeif __name__ == '__main__': a = [1, 5, 5, 1, 6, 1] n = len(a) printLastOccurrence(a, n)# This code is contributed by# Surendra_Gangwar |
C#
// C# program to print the // last occurrence of every // element in relative orderusing System;class GFG{ // Function to print the last // occurrence of every element// in an arraypublic static void printLastOccurrence(int[] a, int n){ HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); // iterate and store the last // index of every element for (int i = 0; i < n; i++) map.put(a[i], i); for (int i = 0; i < n; i++) { if (map.get(a[i]) == i) Console.Write(a[i] + " "); } }// Driver Codepublic static void Main (){ int[] a = { 1, 5, 5, 1, 6, 1 }; int n = a.Length; printLastOccurrence(a, n);}}// This code is contributed// by ChitraNayal |
PHP
<?php // PHP program to print the last // occurrence of every element // in relative order// Function to print the last// occurrence of every element// in an arrayfunction printLastOccurrence(&$a, $n){ // used in hashing $mp = array(); // iterate and store the last // index of every element for ($i = 0; $i < $n; $i++) $mp[$a[$i]] = $i; // iterate and check for the last // occurrence of every element for ($i = 0; $i < $n; $i++) { if ($mp[$a[$i]] == $i) echo $a[$i] . " "; }}// Driver Code$a = array(1, 5, 5, 1, 6, 1);$n = sizeof($a);printLastOccurrence($a, $n);// This code is contributed // by ChitraNayal?> |
Javascript
<script>// Javascript program to print the last// occurrence of every element// in relative order// Function to print the last// occurrence of every element// in an arrayfunction printLastOccurrence(a, n){ // used in hashing let mp = []; // iterate and store the last // index of every element for (let i = 0; i < n; i++) mp[a[i]] = i; // iterate and check for the last // occurrence of every element for (let i = 0; i < n; i++) { if (mp[a[i]] == i) document.write( a[i] + " "); }}// Driver Codelet a = [1, 5, 5, 1, 6, 1];let n = a.length;printLastOccurrence(a, n);// This code is contributed by sravan kumar</script> |
Output
5 6 1
Complexity Analysis:
- Time Complexity: O(N)
- Auxiliary Space: O(N)
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!
