Find the lexicographically largest array containing all distinct elements from each prefix of the given array
Given an array arr[] of length N. The task is to find a lexicographically largest array res[] of the same length such that each prefix of res[] includes all distinct elements present in the corresponding prefix of array arr[].
Examples:
Input: N = 6, arr[] = {2, 5, 3, 2, 6, 5}
Output: res[] = {2, 5, 3, 6, 6, 6}
Explanation: This can be verified that each distinct element of arr[] is present at least once in res[]. Along with this let us analyze each prefix of arr[] for second condition:
- arr[1, 1] = {2}, res[1, 1] = {2}. Each element of prefix arr[] is present at least once in res[]
- arr[1, 2] = {2, 5}, res[1, 2] = {2, 5}. Each element of prefix arr[] is present at least once in res[]
- arr[1, 3] = {2, 5, 3}, res[1, 3] = {2, 5, 3}. Each element of prefix arr[] is present at least once in res[]
- arr[1, 4] = {2, 5, 3, 6} res[1, 4] = {2, 5, 3, 6}. Each element of prefix arr[] is present at least once in res[]
- arr[1, 5] = {2, 5, 3, 6, 6}, res[1, 5] = {2, 5, 3, 6, 6}. Each element of prefix arr[] is present at least once in res[]
- arr[1, 6] = {2, 5, 3, 6, 6, 6}, res[1, 6] = {2, 5, 3, 6, 6, 6}. Each element of prefix arr[] is present at least once in res[]
It can be verified that both the conditions met and res[] is also lexographically largest. Thus, res[] is valid.
Input: N = 4, arr[] = {5, 5, 2, 7}
Output: res[] = {5, 7, 2, 7}
Explanation: It can be verified that res[] is lexographically largest following the condition that each prefix of res[1, i] contains each element of arr[1, i] for all i (1 <= i <=N) at least once.
Approach:
According to the problem, it is given that every element in the prefix arr[] should be present at least once in res[]. So, in the case of multiple occurrences of any element of arr, we need to replace that with the maximum element in arr to make it lexicographically highest. Anyway, it is present once, so for the rest of the occurrences, we can make them to maximum.
Steps-by-step approach:
- Create a result array res[] to store the required order of all elements following given constraints.
- Create a HashMap Map to keep track of occurrences of elements of arr[].
- Create a variable M and initialize it with maximum element of arr[].
- Iterate on arr[] using loop and follow below-mentioned steps under the scope of loop:
- If (arr[i] element is not present in Map)
- Insert element into res[].
- Otherwise,
- Insert the maximum element (M) of the array arr[] into res[].
- Increment the frequency of arr[i] element.
- If (arr[i] element is not present in Map)
- Output all the elements stored in res[].
Below is the implementation of the above approach:
C++
// C++ program to implement the above approach #include <bits/stdc++.h> using namespace std; // Function to find the // lexicographically largest array res[] void MaxLexographicalY( int arr[], int N) { // Vector to store the order of elements // Following the given constraints vector< int > res; // to keep track of occurrances in array A unordered_map< int , int > count; // m is max element of A int m = *max_element(arr, arr + N); for ( int i = 0; i < N; i++) { // if element A[i] not present in map if (!count[arr[i]]) { res.push_back(arr[i]); } else { res.push_back(m); } count[arr[i]]++; } // Printing out all stored elements for ( int i = 0; i < res.size(); i++) { cout << res[i] << ' ' ; } } // Driver Code int main() { // Input int N = 4; int arr[] = { 5, 5, 2, 7 }; // Function Call MaxLexographicalY(arr, N); return 0; } |
Java
/*code by Flutterfly */ import java.util.ArrayList; import java.util.HashMap; public class MaxLexographicalY { // Function to find the lexicographically largest array res[] static void maxLexographicalY( int [] arr, int N) { // ArrayList to store the order of elements // Following the given constraints ArrayList<Integer> res = new ArrayList<>(); // HashMap to keep track of occurrences in array A HashMap<Integer, Integer> count = new HashMap<>(); // m is the max element of A int m = Integer.MIN_VALUE; for ( int value : arr) { m = Math.max(m, value); } for ( int i = 0 ; i < N; i++) { // if element A[i] not present in map if (!count.containsKey(arr[i])) { res.add(arr[i]); } else { res.add(m); } count.put(arr[i], count.getOrDefault(arr[i], 0 ) + 1 ); } // Printing out all stored elements for ( int i = 0 ; i < res.size(); i++) { System.out.print(res.get(i) + " " ); } } // Driver Code public static void main(String[] args) { // Input int N = 4 ; int [] arr = { 5 , 5 , 2 , 7 }; // Function Call maxLexographicalY(arr, N); } } |
Python3
# code by flutterfly from collections import defaultdict # Function to find the lexicographically largest array res[] def max_lexographical_y(arr, N): # List to store the order of elements # Following the given constraints res = [] # Dictionary to keep track of occurrences in array A count = defaultdict( int ) # m is the max element of A m = max (arr) for i in range (N): # if element A[i] not present in map if not count[arr[i]]: res.append(arr[i]) else : res.append(m) count[arr[i]] + = 1 # Printing out all stored elements for i in range ( len (res)): print (res[i], end = ' ' ) # Driver Code if __name__ = = "__main__" : # Input N = 4 arr = [ 5 , 5 , 2 , 7 ] # Function Call max_lexographical_y(arr, N) |
C#
// code by flutterfly using System; using System.Collections.Generic; using System.Linq; class Program { // Function to find the lexicographically largest array res[] static void MaxLexographicalY( int [] arr, int N) { // List to store the order of elements // Following the given constraints List< int > res = new List< int >(); // Dictionary to keep track of occurrences in array A Dictionary< int , int > count = new Dictionary< int , int >(); // m is the max element of A int m = arr.Max(); for ( int i = 0; i < N; i++) { // if element A[i] not present in map if (!count.ContainsKey(arr[i])) { res.Add(arr[i]); } else { res.Add(m); } count[arr[i]] = count.GetValueOrDefault(arr[i]) + 1; } // Printing out all stored elements foreach ( int element in res) { Console.Write(element + " " ); } } // Driver Code static void Main() { // Input int N = 4; int [] arr = { 5, 5, 2, 7 }; // Function Call MaxLexographicalY(arr, N); } } |
Javascript
//code by Flutterfly // Function to find the lexicographically largest array res[] function maxLexographicalY(arr, N) { // Array to store the order of elements // Following the given constraints let res = []; // Map to keep track of occurrences in array A let count = new Map(); // m is the max element of A let m = Math.max(...arr); for (let i = 0; i < N; i++) { // if element A[i] not present in map if (!count.has(arr[i])) { res.push(arr[i]); } else { res.push(m); } count.set(arr[i], (count.get(arr[i]) || 0) + 1); } // Printing out all stored elements on the same line with spaces console.log(res.join( ' ' )); } // Driver Code function main() { // Input let N = 4; let arr = [5, 5, 2, 7]; // Function Call maxLexographicalY(arr, N); } // Invoke the main function main(); |
5 7 2 7
Time Complexity: O(N)
Auxiliary Space: O(N)