Find Anagram Mappings


@oorja your solution is correct but is O(n^2) in time complexity (O(1) extra space). Call to index(i) is O(n) and you are doing it for every element in A.



not sure if the algorithm is correct.
Please check this input
int[] A = {12, 28, 28,28};
int[] B = {28, 28, 12, 28};
output is {2,3,3,3}I think one valid response should be like: {2,0,1,3}
public int[] anagramMappings_(int[] A, int[] B) { HashMap<Integer,List<Integer>> map = new HashMap<>(); for(int i = 0;i< B.length;i++){ List<Integer> m =map.getOrDefault(B[i], new ArrayList<>()); m.add(i); map.put(B[i],m); } int[] M = new int[A.length]; for(int i = 0;i<A.length;i++){ List<Integer> m = map.get(A[i]); if(m != null && m.size() > 0){ M[i] = m.remove(0); if(m.size() == 0 ){ map.remove(A[i]); } } } return M; }


According to the Description:
 "B is an anagram of A means B is made by randomizing the order of the elements in A. "
 "These lists A and B may contain duplicates. If there are multiple answers, output any of them. "
{2,0,1,3} is just one of the answers while
int[] A = {12, 28, 28,28};
int[] B = {28, 28, 12, 28};

class Solution {
public int[] anagramMappings(int[] A, int[] B) {
List<Integer> ret = new ArrayList<Integer>();
List<Integer> listB = new ArrayList<Integer>();
for(int i=0;i<B.length;i++){
listB.add(B[i]);
}
for(int j=0;j<A.length;j++){
if(listB.indexOf(A[j])>1){
ret.add(listB.indexOf(A[j]));
}
}int[] array = new int[ret.size()]; for(int k=0;k<ret.size();k++){ array[k] = ret.get(k); } return array; }
}

javascript:
var anagramMappings = function(A, B) { var r = []; A.forEach(item => r.push(B.indexOf(item))); return r; };
python
class Solution: def anagramMappings(self, A, B): """ :type A: List[int] :type B: List[int] :rtype: List[int] """ r = [] for v in A: r.append(B.index(v)) return r
ruby:
def anagram_mappings(a, b) a.map {v b.find_index(v)} end
golang
func anagramMappings(A []int, B []int) []int { result := make([]int,len(A)) for i,v := range A{ index := getIndex(B, v) result[i] = index } return result } func getIndex(array []int, element int) (r int){ for i, v := range array{ if v == element { r = i break } } return }

@mayasky.wu said in Find Anagram Mappings:
I think the space complexity is not O(N) because the space taken by Hashmap should be considered.
Then what do you think it is?

This solution doesn't handle duplicate entries in the input, consider this input: [1, 1, 2, 3] [2, 3, 1, 1]
This solution return: [3,3,0,1], which doesn't doesn't map the element at index 2.
Here's a suggested solution that gives this answer: [2,3,0,1]class Solution {
public:
vector<int> anagramMappings(vector<int>& A, vector<int>& B)
{vector<int> res(A.size(), 0); for(int i = 0; i < A.size(); i++) {res[i] = i;} for(int i = 0; i < res.size(); i++) { if(B[res[i]] != A[i]) { for(int j = i+1; i < res.size(); j++) { if(B[res[j]] == A[i]) { swap(res[i], res[j]); break; } } } } return res; }
};

I was wondering of an extension/generalization of this problem. Here we are asked to find a solution (one solution). What if we are asked, how many solutions are possible? i.e. the count of possible solutions?
Since elements could repeat, there could certainly be multiple solutions.For our extended question, lets say we are allowed to have indices repeated in the solution (I saw that the expected solution in here does have it repeated). So, [3,4,3,2,3] could be a valid solution to a given problem. So, below is the approach that I am taking:
Construct a dictionary of all the values in B. Here, key is the value in B and the corresponding dictionary value is the list of indices the value is present in B. Note that this is similar to approach #1 proposed above but here we store all the indices of a value, instead of only one. Lets say there are k different distinct values in B (and of course also in A), we have k keys in our dictionary. Let these distinct keys be m1, m2, ..., mk and the count of indices for each (i.e. the number of times a value is repeating) are p1, p2, ..., pk.
For e.g. if B = [50,50,32,50,28], then k = 3.
m1 = 50; p1 = 3, m2 = 32; p2 = 1, m3 = 28; p3 = 1, then, in general, there could be:
"p1^p1 * p2^p2 * ... * pk^pk" possible solutions.
So, for the example above, there are 3^3 * 1^1 * 1^1 = 27 possible solutions.