Generate an array using given conditions from a given array

Last Updated : 15 Sep, 2022

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(N²)
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 conditions
void 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 code
int 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 conditions
import 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 conditions
def 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 code
arr = [ 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 conditions
 
using 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 conditions
function 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 code
let arr = [ 1, 2, 1, 2 ];
let n = arr.length
 
newArray(arr, n);
 
// This code is contributed by phasing17.

Output:

3 2 1 2

Time Complexity: O(n)

Auxiliary Space: O(n)

Check if a string is made up of K alternating characters

Sanjit_Prasad

Improve

Article Tags :

Practice Tags :

Generate an array using given conditions from a given array

CPP

Java

Python3

C#

Javascript

Similar Reads

What kind of Experience do you want to share?