The question deals with a collection of lists L = {h In. Each contains some numb

Question

The question deals with a collection of lists L = {h In. Each contains some number of integers integers, each between 1 and 106. Two lists are identical if they contain the same numbers, maybe not in the same order. For example, the lists h = {10,30,20} and 2 20,10,30 are identical. Let mi be the length of li (for i 1 . . . n). Suggest an algorithm, as efficient as possible, that receives collection of n lists, and de- termines whether the input contains at least two identical lists. Analyze the algorithm's running time. (as a function of n and of mi). It is quite possible the that sum of number is one list is equal to the sum of keys in another list, despite not being identical lists More examples: 10,30, 20 is not identical to l430, 10,30,20 1,-(55.30, 20.30.55) is identical to 15-(55, 30, 55, 20, 30}

Explanation / Answer

Efficient solution of this approach is to use hashing. We store all elements of list one and their counts in a hash table. Then we traverse list two and check if count of every element in list one matches with count in list two.

Algorithm:

If Size of list [0] equals list[1], list[2]… list[n-1]

If its equal, then It implies that the lists are equal, else not.

If yes increment the counter or break from the loop.

Time complexity analysis:

For- traversing list [0] to list[n-1]: O(n)

Combining above two for worst case: O(n)(O(n) + O(n))

** Space complexity O(nm) for n list items, m times in the collection

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.