Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

Minimum Common Value (easy)

Problem Statement

Given two sorted arrays nums1 and nums2 containing integers only, return the smallest integer that appears in both arrays. If there isn't any integer that exists in both arrays, the function should return -1.

Examples

Example 1:

  • input: nums1 = [1, 3, 5, 7], nums2 = [3, 4, 5, 6, 8, 10]
  • expectedOutput: 3
  • Justification: Both arrays share the integers 3 and 5, but the smallest common integer is 3.

Example 2:

  • input: nums1 = [2, 4, 6], nums2 = [1, 3, 5]
  • expectedOutput: -1

.....

.....

.....

Like the course? Get enrolled and start learning!
Konstantin Parakhin

Konstantin Parakhin

· 2 years ago

As both arrays are sorted in ascending order, our minimum common number should be somewhere in the beginning of both arrays. We could just use two pointers and just iterate over both arrays keeping pointer values as close as possible. If we're out of one of arrays, that means they don't have common values.

Complexity of the solution is O(N + K), where N is len(nums1) and K is len(nums2)

class Solution:
    def findMinimumCommonValue(self, nums1, nums2):
        i1, i2 = 0, 0

        while i1 < len(nums1) and i2 < len(nums2):
            if nums1[i1] == nums2[i2]:
                return nums1[i1]
            
            if nums1[i1] > nums2[i2]:
                i2 += 1
            else:
                i1 += 1

        return -1