Horje
Creating Array of Absolute Position Differences for Equal Elements

Given an array arr[] of size N. The task is to create a new array result[] of the same size, where result[i] = ∑ |i – j| for all j such that arr[i] = arr[j].

Examples:

Input: arr = {2, 1, 4, 1, 2, 4, 4}
Output: {4, 2, 7, 2, 4, 4, 5}
Explanation:
=> 0th Index: Another 2 is found at index 4. |0 – 4| = 4
=> 1st Index: Another 1 is found at index 3. |1 – 3| = 2
=> 2nd Index: Two more 4s are found at indices 5 and 6. |2 – 5| + |2 – 6| = 7
=> 3rd Index: Another 1 is found at index 1. |3 – 1| = 2
=> 4th Index: Another 2 is found at index 0. |4 – 0| = 4
=> 5th Index: Two more 4s are found at indices 2 and 6. |5 – 2| + |5 – 6| = 4
=> 6th Index: Two more 4s are found at indices 2 and 5. |6 – 2| + |6 – 5| = 5

Input: arr = {1, 10, 510, 10}
Output: {0, 5, 0, 3, 4}

Constructing an Element Summation Array using Hashing:

To compute result[i], we can apply the following approach:

  • Compute leftFreq, the frequency of the same elements to the left of index i.
  • Calculate leftSum, the summation of indices where the same element occurs to the left of index i.
  • Compute rightSum, the summation of indices where the same element occurs to the right of index i.
  • Calculate rightFreq, the frequency of the same elements to the right of index i.
  • Compute result[i] using the formula: result[i] = ((leftFreq * i) – leftSum) + (rightSum – (rightFreq * i))

Illustration:

Consider the input arr = {3, 2, 3, 3, 2, 3}

Now, If have to calculate the result for the index i = 3 which is element 3.

  • To calculate the absolute value of the required result from the left would be something like => (i – 0) + (i – 2) , which is equals to (2 * i – (0 + 2)).
  • To generalise these, we can generate a formula to do the same: (frequency of similar element to the left* i) – (Sum of occurances of such indices).
  • To calculate the absolute value of required result from the right would be something like => (5 – i)
  • To generalise these, we can generate a formula to do the same: (Sum of occurances of such indices) – (frequency of similar element to the right* i)
  • We can conclude from the above that: The result for the ith index would be:
  • result[i] = ((leftFreq * i) – leftSum) + (rightSum – (rightFreq * i)).

Step-by-step approach:

  • Initialize a map “unmap” of <key, pair<total frequency, total sum>>.
  • Initialize another map unmap2 of <key, pair< frequency till any index i, sum till ith index>>.
  • Iterate over the given array and update the unmap.
  • Create an array result[] for storing the answer
  • Iterate over the given array
    • Update the result[i] = ((leftFreq * i) – leftSum) + (rightSum – (rightFreq * i)).
    • Update the unmap2 by increasing the current element’s frequency and the sum of all occurrences of similar elements till the ith index.
  • Finally, return the result[] as the required answer.

Below is the implementation of the above approach:

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the resultant array
vector<long long> solve(vector<long long>& arr)
{
    int n = arr.size();
 
    // Declare a unordered map unmap for
    // storing the <key, <Total frequency,
    // total sum>> Declare a unordered map
    // unmap2 for storing the <key,
    // <frequency till any index i, sum
    // till ith index>>
    unordered_map<int, pair<long long, long long> > unmap,
        unmap2; // < key, <freq, sum>>
 
    // Iterate over the array and
    // update the unmap
    for (int i = 0; i < n; i++) {
        unmap[arr[i]] = { unmap[arr[i]].first + 1,
                        unmap[arr[i]].second + i };
    }
 
    // Declare an array result for
    // storing the result
    vector<long long> result(n);
 
    // Iterate over the given array
    for (int i = 0; i < n; i++) {
        auto curr = unmap2[arr[i]];
 
        long long leftSum = curr.second;
        long long leftFreq = curr.first;
 
        long long rightSum
            = unmap[arr[i]].second - leftSum - i;
        long long rightFreq
            = unmap[arr[i]].first - leftFreq - 1;
 
        // Update the result[i] with value mentioned
        result[i] = ((leftFreq * i) - leftSum)
                    + (rightSum - (rightFreq * i));
 
        // Update the unmap2 by increasing
        // the current elements frequency
        // and sum of all occurance of
        // similar element till ith index.
        unmap2[arr[i]] = { unmap2[arr[i]].first + 1,
                        unmap2[arr[i]].second + i };
    }
 
    // Finally return result.
    return result;
}
 
// Driver code
int main()
{
    vector<long long> arr = { 2, 1, 4, 1, 2, 4, 4 };
 
    // Function call
    vector<long long> result = solve(arr);
 
    for (auto i : result) {
        cout << i << " ";
    }
 
    return 0;
}

Java

import java.util.HashMap;
import java.util.Map;
import java.util.Vector;
 
public class Main {
    // Function to find the resultant array
    static Vector<Long> solve(Vector<Long> arr)
    {
        int n = arr.size();
 
        // Declare a map for storing the <key, <Total
        // frequency, total sum>>.
        Map<Long, Pair<Long, Long> > unmap
            = new HashMap<>();
        // Declare a map for storing the <key, <frequency
        // till any index i, sum till ith index>>.
        Map<Long, Pair<Long, Long> > unmap2
            = new HashMap<>();
 
        // Iterate over the array and update the unmap
        for (int i = 0; i < n; i++) {
            long key = arr.get(i);
            Pair<Long, Long> value = unmap.getOrDefault(
                key, new Pair<>(0L, 0L));
            unmap.put(key, new Pair<>(value.first + 1,
                                      value.second + i));
        }
 
        // Declare an array result for storing the result
        Vector<Long> result = new Vector<>(n);
 
        // Iterate over the given array
        for (int i = 0; i < n; i++) {
            long key = arr.get(i);
            Pair<Long, Long> curr = unmap2.getOrDefault(
                key, new Pair<>(0L, 0L));
 
            long leftSum = curr.second;
            long leftFreq = curr.first;
 
            Pair<Long, Long> value = unmap.get(key);
            long rightSum = value.second - leftSum - i;
            long rightFreq = value.first - leftFreq - 1;
 
            // Update the result[i] with value mentioned
            result.add(((leftFreq * i) - leftSum)
                       + (rightSum - (rightFreq * i)));
 
            // Update the unmap2 by increasing the current
            // elements frequency and sum of all occurrences
            // of similar elements till ith index.
            unmap2.put(key, new Pair<>(curr.first + 1,
                                       curr.second + i));
        }
 
        // Finally return result.
        return result;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        Vector<Long> arr = new Vector<>();
        arr.add(2L);
        arr.add(1L);
        arr.add(4L);
        arr.add(1L);
        arr.add(2L);
        arr.add(4L);
        arr.add(4L);
 
        // Function call
        Vector<Long> result = solve(arr);
 
        // Print the result
        for (long i : result) {
            System.out.print(i + " ");
        }
    }
 
    static class Pair<T, U> {
        T first;
        U second;
 
        Pair(T first, U second)
        {
            this.first = first;
            this.second = second;
        }
    }
}

Python3

from typing import List, Tuple
 
def solve(arr: List[int]) -> List[int]:
    n = len(arr)
 
    # Declare a dictionary for storing the <key, <Total frequency, total sum>>.
    unmap = {}
    # Declare a dictionary for storing the <key, <frequency till any index i, sum till ith index>>.
    unmap2 = {}
 
    # Iterate over the array and update the unmap
    for i in range(n):
        key = arr[i]
        value = unmap.get(key, (0, 0))
        unmap[key] = (value[0] + 1, value[1] + i)
 
    # Declare a list result for storing the result
    result = []
 
    # Iterate over the given array
    for i in range(n):
        key = arr[i]
        curr = unmap2.get(key, (0, 0))
 
        leftSum, leftFreq = curr[1], curr[0]
 
        value = unmap[key]
        rightSum = value[1] - leftSum - i
        rightFreq = value[0] - leftFreq - 1
 
        # Update the result[i] with value mentioned
        result.append(((leftFreq * i) - leftSum) + (rightSum - (rightFreq * i)))
 
        # Update the unmap2 by increasing the current
        # elements frequency and sum of all occurrences
        # of similar elements till ith index.
        unmap2[key] = (curr[0] + 1, curr[1] + i)
 
    # Finally return result.
    return result
 
# Driver code
if __name__ == "__main__":
    arr = [2, 1, 4, 1, 2, 4, 4]
 
    # Function call
    result = solve(arr)
 
    # Print the result
    print(*result)

C#

using System;
using System.Collections.Generic;
 
class GFG
{
    public static List<long> Solve(List<long> arr)
    {
        int n = arr.Count;
        var unmap = new Dictionary<long, Tuple<long, long>>();
        var unmap2 = new Dictionary<long, Tuple<long, long>>();
 
        for (int i = 0; i < n; i++)
        {
            long key = arr[i];
            if (!unmap.TryGetValue(key, out var value))
            {
                value = new Tuple<long, long>(0, 0);
            }
            unmap[key] = new Tuple<long, long>(value.Item1 + 1, value.Item2 + i);
        }
 
        List<long> result = new List<long>();
 
        for (int i = 0; i < n; i++)
        {
            long key = arr[i];
            if (!unmap2.TryGetValue(key, out var curr))
            {
                curr = new Tuple<long, long>(0, 0);
            }
 
            long leftSum = curr.Item2;
            long leftFreq = curr.Item1;
 
            var value = unmap[key];
            long rightSum = value.Item2 - leftSum - i;
            long rightFreq = value.Item1 - leftFreq - 1;
 
            result.Add(((leftFreq * i) - leftSum) + (rightSum - (rightFreq * i)));
 
            unmap2[key] = new Tuple<long, long>(curr.Item1 + 1, curr.Item2 + i);
        }
 
        return result;
    }
 
    static void Main(string[] args)
    {
        List<long> arr = new List<long> { 2, 1, 4, 1, 2, 4, 4 };
        List<long> result = Solve(arr);
        foreach (var item in result)
        {
            Console.Write(item + " ");
        }
    }
}

Javascript

// Function to find the resultant array
function solve(arr) {
    const n = arr.length;
 
    // Declare a Map for storing the <key, <Total frequency, total sum>>
    const unmap = new Map();
    // Declare a Map for storing the <key, <frequency till any index i, sum till ith index>>
    const unmap2 = new Map();
 
    // Iterate over the array and update the unmap
    for (let i = 0; i < n; i++) {
        const key = arr[i];
        if (!unmap.has(key)) {
            unmap.set(key, [0, 0]);
        }
        const [freq, sum] = unmap.get(key);
        unmap.set(key, [freq + 1, sum + i]);
    }
 
    // Declare an array result for storing the result
    const result = [];
 
    // Iterate over the given array
    for (let i = 0; i < n; i++) {
        const key = arr[i];
        const curr = unmap2.get(key) || [0, 0];
 
        const leftSum = curr[1];
        const leftFreq = curr[0];
 
        const [freq, sum] = unmap.get(key);
        const rightSum = sum - leftSum - i;
        const rightFreq = freq - leftFreq - 1;
 
        // Update the result[i] with value mentioned
        result.push((leftFreq * i) - leftSum + rightSum - (rightFreq * i));
 
        // Update the unmap2 by increasing the current element's frequency
        // and sum of all occurrences of a similar element till ith index.
        unmap2.set(key, [curr[0] + 1, curr[1] + i]);
    }
 
    // Finally return result.
    return result;
}
 
// Driver code
const arr = [2, 1, 4, 1, 2, 4, 4];
 
// Function call
const result = solve(arr);
 
console.log(result.join(' '));
 
// This code is contributed by rambabuguphka

Output

4 2 7 2 4 4 5

Time Complexity: O(N)
Auxiliary space: O(N)


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Minimizing Swaps for Adjacent pair Sum Difference in Permutation Minimizing Swaps for Adjacent pair Sum Difference in Permutation
Difference of Max and Min Subtree Sums in Tree Nodes Difference of Max and Min Subtree Sums in Tree Nodes
Minimum days to make M bouquets Minimum days to make M bouquets
Finding Nearest Stores for each Houses Finding Nearest Stores for each Houses
Find a pair with difference between Values and Indices in the Array Find a pair with difference between Values and Indices in the Array

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 11



 

Horje