Finding Common Elements (Amazon SDE-1)

Question

Given two lists V1 and V2 of sizes n and m respectively. Return the list of elements common to both the lists and return the list in sorted order. Duplicates may be there in the output list.

Link to the problem : LINK

Example:

Input:
5
3 4 2 2 4
4
3 2 2 7

Output:
2 2 3

Explanation:
The first list is {3 4 2 2 4}, and the second list is {3 2 2 7}. 
The common elements in sorted order are {2 2 3}

Expected Time complexity : O(N)

My code:

class Solution:
    def common_element(self,v1,v2):
        dict1 = {}
        ans = []
        
        for num1 in v1:
            dict1[num1] = 0
            
        for num2 in v2:
            if num2 in dict1:
                ans.append(num2)
                
        return sorted(ans)

Problem with my code: So the accessing time in a dictionary is constant and hence my time complexity was reduced but one of the hidden test cases is failing and my logic is very simple and straight forward and everything seems to be on point. What's your take? Is the logic wrong or the question desc is missing some vital details?

New Approach Now I am generating two hashmaps/dictionaries for the two arrays. If a num is present in another array, we check the min frequency and then appending that num into the ans that many times.

 class Solution:
    def common_element(self,arr1,arr2):
        
        dict1 = {}
        dict2 = {}
        ans = []
    
        for num1 in arr1:
            dict1[num1] = 0
        for num1 in arr1:
            dict1[num1] += 1
    
        for num2 in arr2:
            dict2[num2] = 0
        for num2 in arr2:
            dict2[num2] += 1
    
        for number in dict1:
            if number in dict2:
                minFreq = min(dict1[number],dict2[number])
                
                for _ in range(minFreq):
                    ans.append(number)
    
        return sorted(ans)

The code is outputting nothing for this test case

Input:
64920
83454 38720 96164 26694 34159 26694 51732 64378 41604 13682 82725 82237 41850 26501 29460 57055 10851 58745 22405 37332 68806 65956 24444 97310 72883 33190 88996 42918 56060 73526 33825 8241 37300 46719 45367 1116 79566 75831 14760 95648 49875 66341 39691 56110 83764 67379 83210 31115 10030 90456 33607 62065 41831 65110 34633 81943 45048 92837 54415 29171 63497 10714 37685 68717 58156 51743 64900 85997 24597 73904 10421 41880 41826 40845 31548 14259 11134 16392 58525 3128 85059 29188 13812.................

Its Correct output is:
4 6 9 14 17 19 21 26 28 32 33 42 45 54 61 64 67 72 77 86 93 108 113 115 115 124 129 133 135 137 138 141 142 144 148 151 154 160 167 173 174 192 193 195 198 202 205 209 215 219 220 221 231 231 233 235 236 238 239 241 245 246 246 247 254 255 257 262 277 283 286 290 294 298 305 305 307 309 311 312 316 319 321 323 325 325 326 329 329 335 338 340 341 350 353 355 358 364 367 369 378 385 387 391 401 404 405 406 406 410 413 416 417 421 434 435 443 449 452 455 456 459 460 460 466 467 469 473 482 496 503 .................

And Your Code's output is:

user_13477216 · Answer

Please find the below solution

def sorted_common_elemen(v1, v2):
    res = []
    for elem in v2:
        res.append(elem)
        v1.pop(0)

    return sorted(res)

user_15146772 · Answer

Your code ignores the number of times a given element occurs in the list. I think this is a good way to fix that:

class Solution:
    def common_element(self, l0, l1):
        li = []
        for i in l0:
           if i in l1:
               l1.remove(i)
               li.append(i)
        return sorted(li)

Finding Common Elements (Amazon SDE-1)

2 Answers