Jobs

Interviews

Discussions

Minimum Common Value

Easy

Asked by:

More companies

22 views

Topics:

ArraysTwo Pointers

Given two integer arrays nums1 and nums2, sorted in non-decreasing order, return the minimum integer common to both arrays. If there is no common integer amongst nums1 and nums2, return -1.

Note that an integer is said to be common to nums1 and nums2 if both arrays have at least one occurrence of that integer.

Example 1:

Input: nums1 = [1,2,3], nums2 = [2,4]
Output: 2
Explanation: The smallest element common to both arrays is 2, so we return 2.

Example 2:

Input: nums1 = [1,2,3,6], nums2 = [2,3,4,5]
Output: 2
Explanation: There are two common elements in the array 2 and 3 out of which 2 is the smallest, so 2 is returned.

Constraints:

1 <= nums1.length, nums2.length <= 10⁵
1 <= nums1[i], nums2[j] <= 10⁹
Both nums1 and nums2 are sorted in non-decreasing order.

Try coding it in LeetCode

Minimum Common Value

Easy

Asked by:

22 views

Topics:

ArraysTwo Pointers

Note that an integer is said to be common to nums1 and nums2 if both arrays have at least one occurrence of that integer.

Example 1:

Input: nums1 = [1,2,3], nums2 = [2,4]
Output: 2
Explanation: The smallest element common to both arrays is 2, so we return 2.

Example 2:

Input: nums1 = [1,2,3,6], nums2 = [2,3,4,5]
Output: 2
Explanation: There are two common elements in the array 2 and 3 out of which 2 is the smallest, so 2 is returned.

Constraints:

1 <= nums1.length, nums2.length <= 10⁵
1 <= nums1[i], nums2[j] <= 10⁹
Both nums1 and nums2 are sorted in non-decreasing order.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected return value if the two arrays have no common values?
Can the input arrays contain duplicate values, and if so, should I return a common value only once?
Are the input arrays guaranteed to be sorted in ascending order?
What is the range of possible integer values within the arrays? Could there be any potential for integer overflow?
Can either of the input arrays be empty or null?

Brute Force Solution

Approach

The brute force method is like manually comparing every single item in two lists to see if any match. We go through each number in the first list and check if it exists anywhere in the second list. If we find a match, we've found our answer.

Here's how the algorithm would work step-by-step:

Start with the first number in the first list.
Look at every single number in the second list to see if it's the same as the number from the first list.
If you find a matching number, you've found the minimum common value. Stop looking and tell me what that number is.
If you go through the entire second list and don't find a match, move on to the next number in the first list.
Repeat the process of comparing this new number from the first list to every number in the second list.
Continue until you either find a common number or you've checked all the numbers in the first list.

Code Implementation

def minimum_common_value_brute_force(first_list, second_list):
    for first_list_index in range(len(first_list)):
        first_list_number = first_list[first_list_index]

        # Need to iterate through the entire second list
        for second_list_index in range(len(second_list)):
            second_list_number = second_list[second_list_index]

            # Found a common value, return it immediately
            if first_list_number == second_list_number:
                return first_list_number

    # No common values were found
    return -1

Big(O) Analysis

Time Complexity

O(n*m) – The described brute force approach iterates through each element of the first list, which we can assume has a size of 'n'. For each of these 'n' elements, the algorithm iterates through the entirety of the second list, which we can assume has a size of 'm', to check for a match. Therefore, in the worst-case scenario where no common value is found until the very end or doesn't exist, the number of comparisons performed is proportional to n * m. Thus, the time complexity is O(n*m).

Space Complexity

O(1) – The brute force approach iterates through the two input lists, comparing elements directly without creating any additional data structures. No temporary arrays, hash maps, or significant extra variables beyond a few loop indices are used. The space required remains constant irrespective of the input arrays' sizes. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The goal is to find the smallest number that appears in both lists. We can efficiently find this number by walking through both lists at the same time, like merging sorted lists. This avoids looking at unnecessary numbers and quickly finds the first shared value.

Here's how the algorithm would work step-by-step:

Start by looking at the beginning of both number lists.
If the number in the first list is smaller than the number in the second list, move to the next number in the first list.
If the number in the second list is smaller than the number in the first list, move to the next number in the second list.
If the numbers are the same, you've found the smallest shared number! Return that number.
Keep doing this until you find a common number or reach the end of either list. If you reach the end of either list without finding a match, there is no common number.

Code Implementation

def find_minimum_common_value(first_list, second_list):
    first_list_index = 0
    second_list_index = 0

    while first_list_index < len(first_list) and second_list_index < len(second_list):
        #If value in first list is smaller, increment index
        if first_list[first_list_index] < second_list[second_list_index]:
            first_list_index += 1

        #If value in second list is smaller, increment index
        elif second_list[second_list_index] < first_list[first_list_index]:
            second_list_index += 1

        else:
            #We found the minimum common value
            return first_list[first_list_index]

    return -1

Big(O) Analysis

Time Complexity

O(n) – The algorithm uses two pointers, each traversing one of the input arrays. In the worst-case scenario, one pointer might traverse almost the entire length of its array while the other pointer also advances. Because each pointer advance represents a comparison, and since both arrays are traversed in a linear manner, the maximum number of comparisons is proportional to the sum of the lengths of the two arrays. Assuming both arrays have a maximum length of 'n', the time complexity can be approximated as O(n).

Space Complexity

O(1) – The algorithm utilizes two index variables to traverse the input lists. The number of index variables does not scale with the size of the input lists. Therefore, the auxiliary space required remains constant regardless of the input size, making the space complexity O(1).

Edge Cases

Case	How to Handle
One or both input arrays are null	Throw IllegalArgumentException or return a specific error value (e.g., -1) to signal invalid input.
One or both input arrays are empty	Return -1 immediately, as there can be no common value.
Arrays contain only one element	Compare the single elements and return the value if they are equal, otherwise return -1.
Arrays contain large numbers (potential integer overflow)	Use long data type to perform comparisons to avoid integer overflow issues.
Arrays contain duplicate values	The algorithm should still find the minimum common value correctly, as it iterates through the arrays.
Arrays contain negative numbers	The algorithm should correctly handle negative numbers as long as comparisons are done appropriately.
No common value exists between the two arrays	Return -1 to indicate that no common value was found.
Arrays are very large, exceeding available memory	Consider a streaming approach where you read chunks of data from disk if the arrays are too large to fit in memory.

One or both input arrays are null

How to Handle:

Throw IllegalArgumentException or return a specific error value (e.g., -1) to signal invalid input.

One or both input arrays are empty

How to Handle:

Return -1 immediately, as there can be no common value.

Arrays contain only one element

How to Handle:

Compare the single elements and return the value if they are equal, otherwise return -1.

Arrays contain large numbers (potential integer overflow)

How to Handle:

Use long data type to perform comparisons to avoid integer overflow issues.

Arrays contain duplicate values

How to Handle:

The algorithm should still find the minimum common value correctly, as it iterates through the arrays.

Arrays contain negative numbers

How to Handle:

The algorithm should correctly handle negative numbers as long as comparisons are done appropriately.

No common value exists between the two arrays

How to Handle:

Return -1 to indicate that no common value was found.

Arrays are very large, exceeding available memory

How to Handle:

Consider a streaming approach where you read chunks of data from disk if the arrays are too large to fit in memory.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected return value if the two arrays have no common values?
Can the input arrays contain duplicate values, and if so, should I return a common value only once?
Are the input arrays guaranteed to be sorted in ascending order?
What is the range of possible integer values within the arrays? Could there be any potential for integer overflow?
Can either of the input arrays be empty or null?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the first number in the first list.
Look at every single number in the second list to see if it's the same as the number from the first list.
If you find a matching number, you've found the minimum common value. Stop looking and tell me what that number is.
If you go through the entire second list and don't find a match, move on to the next number in the first list.
Repeat the process of comparing this new number from the first list to every number in the second list.
Continue until you either find a common number or you've checked all the numbers in the first list.

Code Implementation

def minimum_common_value_brute_force(first_list, second_list):
    for first_list_index in range(len(first_list)):
        first_list_number = first_list[first_list_index]

        # Need to iterate through the entire second list
        for second_list_index in range(len(second_list)):
            second_list_number = second_list[second_list_index]

            # Found a common value, return it immediately
            if first_list_number == second_list_number:
                return first_list_number

    # No common values were found
    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the beginning of both number lists.
If the number in the first list is smaller than the number in the second list, move to the next number in the first list.
If the number in the second list is smaller than the number in the first list, move to the next number in the second list.
If the numbers are the same, you've found the smallest shared number! Return that number.
Keep doing this until you find a common number or reach the end of either list. If you reach the end of either list without finding a match, there is no common number.

Code Implementation

def find_minimum_common_value(first_list, second_list):
    first_list_index = 0
    second_list_index = 0

    while first_list_index < len(first_list) and second_list_index < len(second_list):
        #If value in first list is smaller, increment index
        if first_list[first_list_index] < second_list[second_list_index]:
            first_list_index += 1

        #If value in second list is smaller, increment index
        elif second_list[second_list_index] < first_list[first_list_index]:
            second_list_index += 1

        else:
            #We found the minimum common value
            return first_list[first_list_index]

    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
One or both input arrays are null	Throw IllegalArgumentException or return a specific error value (e.g., -1) to signal invalid input.
One or both input arrays are empty	Return -1 immediately, as there can be no common value.
Arrays contain only one element	Compare the single elements and return the value if they are equal, otherwise return -1.
Arrays contain large numbers (potential integer overflow)	Use long data type to perform comparisons to avoid integer overflow issues.
Arrays contain duplicate values	The algorithm should still find the minimum common value correctly, as it iterates through the arrays.
Arrays contain negative numbers	The algorithm should correctly handle negative numbers as long as comparisons are done appropriately.
No common value exists between the two arrays	Return -1 to indicate that no common value was found.
Arrays are very large, exceeding available memory	Consider a streaming approach where you read chunks of data from disk if the arrays are too large to fit in memory.

One or both input arrays are null

How to Handle:

Throw IllegalArgumentException or return a specific error value (e.g., -1) to signal invalid input.

One or both input arrays are empty

How to Handle:

Return -1 immediately, as there can be no common value.

Arrays contain only one element

How to Handle:

Compare the single elements and return the value if they are equal, otherwise return -1.

Arrays contain large numbers (potential integer overflow)

How to Handle:

Use long data type to perform comparisons to avoid integer overflow issues.

Arrays contain duplicate values

How to Handle:

The algorithm should still find the minimum common value correctly, as it iterates through the arrays.

Arrays contain negative numbers

How to Handle:

The algorithm should correctly handle negative numbers as long as comparisons are done appropriately.

No common value exists between the two arrays

How to Handle:

Return -1 to indicate that no common value was found.

Arrays are very large, exceeding available memory

How to Handle:

Consider a streaming approach where you read chunks of data from disk if the arrays are too large to fit in memory.