Solution to first follow up question


  • 1
    S

    What if the given array is already sorted? How would you optimize your algorithm?

    If both the arrays are sorted, we can use two pointers technique. Run time would be O(n+m) with O(1) space complexity.

    Code would look something like below

            i = 0
            j = 0
            res = []
            while i < len(nums1) and j < len(nums2):
                if nums1[i] < nums2[j]:
                    i += 1
                elif nums1[i] > nums2[j]:
                    j += 1
                else:
                    res.append(nums1[i])
                    i += 1
                    j += 1
            
            return res 
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.