CODEWITHSUNDEEP
arraysalgorithmdata-structurespermutationsub-array
Yadnesh Khode
Yadnesh Khode

Reputation: 14

How to solve this permutation related problem in O(n^2) complexity?

There are 2 arrays A and B with lengths N and M you have to delete 1 element at a time from B and check if there exists a permutation of B in A

Explanation: Example:

N = 5
A = [1,2,2,1,1]
M = 3
b = [1,2,1]
Output: [0,2,3]

When you delete 1st element from B it becomes [2,1] you can see in array A the subarray of length 2 starting from index 0 is [1,2] and as [1,2] is the permutation of [2,1] you have a match corresponding to this subarray. Similarly, the subarray starting from index 2 is also a match. So you got 2 matches now corresponding to index 0 and 2. Now the array B is restored B = [1,2,1]

Now when you delete the 2nd element from B it becomes [1,1] for this you can find 1 match corresponding to the subarray starting from index 3

removing 3rd element is of no use as we had removed 1 before and checked for it

Therefore the answer is [0,2,3]

Upvotes: 0

Views: 87

Answers (1)

גלעד ברקן
גלעד ברקן

Reputation: 23955

If we're looking for O(n^2) complexity, hash every window in A, where the key is the sorted list of elements in the window and the values are the indexes, where it's seen. For your example, we'd have:

[1,2,2,1,1]

1,1,1,2,2 -> [0]
1,1,2,2   -> [0, 1]
1,2,2     -> [0, 1]
...
1,2       -> [0, 2]
etc.

we could also use a multiset for a key, if many duplicates are expected, like:

1:3,2:2 -> [0]

Now create a corresponding key for each element deleted in B, as we traverse, and check if the key is in the hash table.

B: {1: 2, 2: 1}

Traverse:

Key 1:1,2:1 -> indexes [0, 2]
...etc.

Upvotes: 1

Related Questions