Given an array arr[] of size N, the task is to construct a new array B[] using elements of array A such that:
- If the element is not present in B[], then append it to the end.
- If the element is present in B[], then first increment its leftmost occurrence by 1 and then append this element to the end of the array.
Examples:
Input: arr[] = {1, 2, 1, 2}
Output: { 3, 2, 1, 2 }
Explanation:
arr[0] = 1, B = {}. 1 is not present in B. So append it at the end. Therefore, B = {1}
arr[1] = 2, B = {1}. 2 is not present in B. So append it at the end. Therefore, B[] = {1, 2}
arr[2] = 1, B = {1, 2}. 1 is already present in B[]. So increment B[0] by 1 and append 1 at the end. Therefore B[] = {2, 2, 1}
arr[3] = 2, B = {2, 2, 1}. 2 is already present in B[]. So increment B[0] by 1 and append 2 at the end. Therefore B[] = {3, 2, 1, 2}
Input: arr[] = {2, 5, 4, 2, 8, 4, 2}
Output: {3, 5, 5, 3, 8, 4, 2}
Naive Approach: For every element in the array A, check if it is present in array B or not. If the element exists, then increment the leftmost occurrence by one. Finally, add the element at the end of the array B[].
Time Complexity: O(N2)
Efficient Approach: The idea is to use a map to store all the indices of every element. The array B[] is generated as:
- For every element in the array arr[], it is checked if the element is already present in the array B[] or not.
- If the element is not present in the array B[], then the element is added to the array B[] and its index is added to the map. Since this is the first occurrence of the element, this index becomes the left-most index of the element.
- If the element is already present in the array B[], then the left-most index is returned and the element at that index is incremented by one. When the value is incremented, the left-most index of the old value is updated along with the index of the new value.
Below is the implementation of the above approach:
CPP
// C++ program to generate an array// from a given array under the// given conditions#include <bits/stdc++.h>using namespace std;// Function to generate an array// from a given array under the// given conditionsvoid newArray(int A[], int n){ // To maintain indexes of the // elements in sorted order unordered_map<int, set<int> > idx; // Initialize new array B std::vector<int> B; // For every element in the given // array arr[] for (int i = 0; i < n; ++i) { // Check if the element is present // in the array B[] if (idx.find(A[i]) != idx.end()) { // Get the leftmost position // in the array B int pos = *idx[A[i]].begin(); // Remove the leftmost position idx[A[i]].erase(idx[A[i]].begin()); // Increment the value at // the leftmost position B[pos]++; // Insert new value position // in the map idx[B[pos]].insert(pos); } // Append arr[i] at the end // of the array B B.push_back(A[i]); // Insert its position in hash-map idx[A[i]].insert(i); } // Print the generated array for (int i = 0; i < n; ++i) cout << B[i] << " ";}// Driver codeint main(){ int arr[] = { 1, 2, 1, 2 }; int n = sizeof(arr) / sizeof(int); newArray(arr, n); return 0;} |
Java
// Java program to generate an array// from a given array under the// given conditionsimport java.util.*;class GFG{ // Function to generate an array // from a given array under the // given conditions static void newArray(int[] A, int n) { // To maintain indexes of the // elements in sorted order HashMap<Integer, HashSet<Integer> > idx = new HashMap<Integer, HashSet<Integer> >(); // Initialize new array B ArrayList<Integer> B = new ArrayList<Integer>(); // For every element in the given // array arr[] for (int i = 0; i < n; ++i) { // Check if the element is present // in the array B[] if (idx.containsKey(A[i])) { // Get the leftmost position // in the array B HashSet<Integer> h1 = idx.get(A[i]); int pos = Collections.min(h1); // Remove the leftmost position h1.remove(pos); idx.put(A[i], h1); // Increment the value at // the leftmost position B.set(pos, B.get(pos) + 1); // Insert new value position // in the map HashSet<Integer> h2; if (!idx.containsKey(B.get(pos))) idx.put(B.get(pos), new HashSet<Integer>()); h2 = idx.get(B.get(pos)); h2.add(pos); idx.put(B.get(pos), h2); h1.add(B.size()); idx.put(A[i], h1); } else { HashSet<Integer> h1 = new HashSet<Integer>(); h1.add(B.size()); idx.put(A[i], h1); } // Append arr[i] at the end // of the array B B.add(A[i]); } // Print the generated array for (int i = 0; i < B.size(); i++) System.out.print(B.get(i) + " "); } // Driver code public static void main(String[] args) { int[] arr = { 1, 2, 1, 2 }; int n = arr.length; newArray(arr, n); }}// This code is contributed by phasing17. |
Python3
# Python3 program to generate an array# from a given array under the# given conditions# Function to generate an array# from a given array under the# given conditionsdef newArray(A, n): # To maintain indexes of the # elements in sorted order idx = dict(); # Initialize new array B B = []; # For every element in the given # array arr[] for i in range(n): # Check if the element is present # in the array B[] if A[i] in idx: # Get the leftmost position # in the array B pos = min(idx[A[i]]) # Remove the leftmost position idx[A[i]].discard(pos) # Increment the value at # the leftmost position B[pos] = B[pos] + 1 # Insert new value position # in the map if B[pos] not in idx: idx[B[pos]] = set() idx[B[pos]].add(pos) idx[A[i]].add(len(B)) else: idx[A[i]] = set() idx[A[i]].add(len(B)) # Append arr[i] at the end # of the array B B.append(A[i]); # Print the generated array print(*B)# Driver codearr = [ 1, 2, 1, 2 ];n = len(arr)newArray(arr, n);# This code is contributed by phasing17. |
C#
// C# program to generate an array// from a given array under the// given conditionsusing System;using System.Linq;using System.Collections.Generic;class GFG { // Function to generate an array // from a given array under the // given conditions static void newArray(int[] A, int n) { // To maintain indexes of the // elements in sorted order Dictionary<int, HashSet<int> > idx = new Dictionary<int, HashSet<int> >(); // Initialize new array B List<int> B = new List<int>(); // For every element in the given // array arr[] for (int i = 0; i < n; ++i) { // Check if the element is present // in the array B[] if (idx.ContainsKey(A[i])) { // Get the leftmost position // in the array B int pos = (idx[A[i]]).Min(c => c); // Remove the leftmost position idx[A[i]].Remove(pos); // Increment the value at // the leftmost position B[pos]++; // Insert new value position // in the map if (!idx.ContainsKey(B[pos])) idx[B[pos]] = new HashSet<int>(); idx[B[pos]].Add(pos); idx[A[i]].Add(B.Count); } else { idx[A[i]] = new HashSet<int>(); idx[A[i]].Add(B.Count); } // Append arr[i] at the end // of the array B B.Add(A[i]); } // Print the generated array for (int i = 0; i < B.Count; i++) Console.Write(B[i] + " "); } // Driver code public static void Main(string[] args) { int[] arr = { 1, 2, 1, 2 }; int n = arr.Length; newArray(arr, n); }}// This code is contributed by phasing17. |
Javascript
// JS program to generate an array// from a given array under the// given conditions// Function to generate an array// from a given array under the// given conditionsfunction newArray(A, n){ // To maintain indexes of the // elements in sorted order let idx = {}; // Initialize new array B let B = []; // For every element in the given // array arr[] for (var i = 0; i < n; ++i) { // Check if the element is present // in the array B[] if (idx.hasOwnProperty(A[i])) { // Get the leftmost position // in the array B let pos = Math.min.apply(this, [...idx[A[i]]]); // Remove the leftmost position idx[A[i]].delete(pos) // Increment the value at // the leftmost position B.splice(pos, 1, B[pos] + 1); // Insert new value position // in the map if (!idx.hasOwnProperty(B[pos])) idx[B[pos]] = new Set() idx[B[pos]].add(pos) idx[A[i]].add(B.length) } else { idx[A[i]] = new Set(); idx[A[i]].add(B.length) } // Append arr[i] at the end // of the array B B.push(A[i]); } // Print the generated array console.log(B.join(" "))}// Driver codelet arr = [ 1, 2, 1, 2 ];let n = arr.lengthnewArray(arr, n);// This code is contributed by phasing17. |
Output:
3 2 1 2
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!
