Knowledge Guide
Home › DSA › Searching

easy Minimum Common Value

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:

Example 2:

Example 3:

Constraints:

Try it yourself

Try solving this question here:

✅ Solution Minimum Common Value

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
  • Justification: There are no integers common to both nums1 and nums2, hence the output is -1.

Example 3:

  • input: nums1 = [1, 2, 2, 3], nums2 = [2, 2, 4]
  • expectedOutput: 2
  • Justification: The integer 2 is the only common number between nums1 and nums2, appearing multiple times in both, and it is the smallest.

Constraints:

  • 1 <= nums1.length, nums2.length <= 105
  • 1 <= nums1[i], nums2[j] <= 109
  • Both nums1 and nums2 are sorted in non-decreasing order.

Solution

To efficiently solve this problem, a binary search algorithm can be employed due to the sorted nature of the input arrays. The binary search approach will be utilized to find the smallest common integer between the two arrays.

We start by iterating through the smaller array and use binary search on the larger array to check for the presence of each element from the smaller array. This ensures that we only search for potential common values and hence minimize the number of comparisons. Using binary search reduces the time complexity significantly compared to a linear search, especially for larger arrays, making this approach both efficient and effective.

Step-by-step Algorithm

  1. Swap Arrays if Necessary:

    • If nums1 is longer than nums2, swap them. This ensures that the binary search is always performed on the larger array, optimizing search efficiency.

  2. Iterate through the Smaller Array:

    • Loop through each element num in the smaller array (nums1).

  3. Binary Search in Larger Array:

    • For each element num, call the binarySearch method on the larger array (nums2).
    • If binarySearch returns True (element found in nums2), immediately return the num as it is the smallest common element found so far.

  4. No Common Element Found:

    • If the loop completes without finding any common element, return -1.

  5. Binary Search Method:

    • Initialize two pointers, left and right, to define the search boundaries.
    • While left is less than or equal to right:
      • Calculate the middle index mid.
      • Compare the target with the element at mid.
      • Adjust the left or right pointers based on the comparison result to narrow the search.
    • If the target is not found by the end of the loop, return False.

Algorithm Walkthrough

Let's consider the input: nums1 = [1, 3, 5, 7], nums2 = [3, 4, 5, 6, 8, 10]

  1. Initial Check:

    • nums1 length is 4 and nums2 length is 6. No need to swap since nums2 is already larger.

  2. Binary Search for 1:

    • Initialize left = 0 and right = 5.
    • Calculate the middle index: mid = (0 + 5) // 2 = 2. The element at mid is nums2[2] = 5.
    • Since nums2[2] (5) is greater than 1, adjust the right pointer: right = mid - 1 = 1.
    • Recalculate mid: mid = (0 + 1) // 2 = 0. The element at mid is nums2[0] = 3.
    • Since nums2[0] (3) is greater than 1, adjust the right pointer again: right = mid - 1 = -1.
    • At this point, left = 0 is greater than right = -1, ending the search. The target 1 is not found.

  3. Binary Search for 3:

    • Found in nums2.
      • Start: left = 0, right = 5, mid = 2 (nums2[2] = 5).
      • nums2[2] > 3, so adjust right to mid - 1 (right = 1).
      • New mid = 0 (nums2[0] = 3).
      • nums2[0] = 3, found the target. Return 3.

  4. Return Value:

    • The smallest common element 3 is returned after the second binary search.
Image
Image

Code

java
public class Solution {

  // Function to find the minimum common value between two arrays
  public int findMinimumCommonValue(int[] nums1, int[] nums2) {
    // Ensure binary search is done on the larger array
    if (nums1.length > nums2.length) {
      return findMinimumCommonValue(nums2, nums1);
    }

    // Search for each element of the smaller array in the larger array
    for (int num : nums1) {
      if (binarySearch(nums2, num)) {
        return num; // Return the common element found
      }
    }

    // If no common elements are found, return -1
    return -1;
  }

  // Binary search method to find if target exists in nums
  private boolean binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    // Continue searching while left pointer is less than or equal to right pointer
    while (left <= right) {
      int mid = left + (right - left) / 2; // Calculate the middle index
      if (nums[mid] > target) {
        right = mid - 1; // If target is less than element at mid, search left half
      } else if (nums[mid] < target) {
        left = mid + 1; // If target is greater than element at mid, search right half
      } else {
        return true; // Target found
      }
    }
    return false; // Target not found
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Test cases
    System.out.println(
      solution.findMinimumCommonValue(
        new int[] { 1, 3, 5, 7 },
        new int[] { 3, 4, 5, 6, 8, 10 }
      )
    ); // Expected Output: 3
    System.out.println(
      solution.findMinimumCommonValue(
        new int[] { 2, 4, 6 },
        new int[] { 1, 3, 5 }
      )
    ); // Expected Output: -1
    System.out.println(
      solution.findMinimumCommonValue(
        new int[] { 1, 2, 2, 3 },
        new int[] { 2, 2, 4 }
      )
    ); // Expected Output: 2
  }
}

Complexity Analysis

  • Time Complexity:
    • The major time-consuming operation in this solution is the binary search performed on the larger array for each element of the smaller array.
    • Since binary search operates in time, where (m) is the length of the larger array, and assuming (n) is the length of the smaller array, the overall time complexity becomes .
  • Space Complexity:
    • The space complexity of the solution is , as the solution only uses a constant amount of extra space for pointers and temporary variables regardless of the input size.
🤖 Don't fully get this? Learn it with Claude

Stuck on Minimum Common Value? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Minimum Common Value** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Minimum Common Value** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Minimum Common Value**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Minimum Common Value**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Maximum Count of Positive Integer Frequency of the Most Frequent Ele →