Solution to first follow up question

  • 1

    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
                    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.