algoadvance

Leetcode 2540. Minimum Common Value

Problem Statement

You are given two integer arrays nums1 and nums2 sorted in non-decreasing order. There is exactly one integer that is common in both arrays. Return this integer. You must write an algorithm with O(log n) runtime complexity.

Clarifying Questions

  1. Is it guaranteed that both arrays will have exactly one integer in common?
    • Yes, this is specified in the problem.
  2. Can the arrays be of different lengths?
    • Yes, the arrays can be of different lengths but they are both sorted.
  3. Are there any constraints on the values or lengths of the arrays?
    • Yes, typical constraints will apply based on problem statement e.g., the size of nums1 and nums2 is within the range [1, 10^4] and the values of elements are within a certain range of integers.

Strategy

Since we need to achieve an O(log n) runtime complexity, a binary search approach is suitable here. One effective way of solving this problem involves using the fact that both arrays are sorted:

  1. Loop through each element in nums1.
  2. For each element in nums1, perform a binary search in nums2 to see if that element exists in nums2.
  3. As soon as we find the common element, we return it.

This approach ensures that we are leveraging the O(log n) property of binary search.

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    int getCommon(std::vector<int>& nums1, std::vector<int>& nums2) {
        for(int num : nums1) {
            if (binarySearch(nums2, num)) {
                return num;
            }
        }
        return -1; // Based on problem constraints this should never happen.
    }

private:
    bool binarySearch(const std::vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return true;
            }
            else if (nums[mid] < target) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return false;
    }
};

Time Complexity

Combining both, the overall time complexity is:

This satisfies the requirement of achieving a logarithmic runtime since one array is traversed linearly while the other is searched logarithmically.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI