Jobs

Interviews

Discussions

Largest Positive Integer That Exists With Its Negative

Easy

Coupang

0 views

Topics:

Arrays

Given an integer array nums that does not contain any zeros, find the largest positive integer k such that -k also exists in the array.

Return the positive integer k. If there is no such integer, return -1.

For example:

nums = [-1,2,-3,3]

Output: 3

Explanation: 3 is the only valid k we can find in the array.

Another example:

nums = [-1,10,6,7,-7,1]

Output: 7

Explanation: Both 1 and 7 have their corresponding negative values in the array. 7 has a larger value.

Finally:

nums = [-10,8,6,7,-2,-3]

Output: -1

Explanation: There is no a single valid k, we return -1.

Write a function that takes an integer array and returns the largest positive integer k such that -k exists in the array. If no such integer exists, return -1. Can you describe the time and space complexity of your solution?

Largest Positive Integer That Exists With Its Negative

Easy

Coupang

0 views

Topics:

Arrays

Given an integer array nums that does not contain any zeros, find the largest positive integer k such that -k also exists in the array.

Return the positive integer k. If there is no such integer, return -1.

For example:

nums = [-1,2,-3,3]

Output: 3

Explanation: 3 is the only valid k we can find in the array.

Another example:

nums = [-1,10,6,7,-7,1]

Output: 7

Explanation: Both 1 and 7 have their corresponding negative values in the array. 7 has a larger value.

Finally:

nums = [-10,8,6,7,-2,-3]

Output: -1

Explanation: There is no a single valid k, we return -1.

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 are the constraints on the size of the input array `nums`?
What is the range of values for the integers within the input array `nums`?
If multiple positive integers `K` satisfy the condition (both `K` and `-K` exist), should I return the largest one, or is any valid `K` acceptable?
Are duplicate numbers allowed in the array? If so, how should duplicates affect the identification of `K`?
If the input array `nums` is empty, what should I return?

Brute Force Solution

Approach

The brute force method for this problem is straightforward. We will check every single number in the list to see if its negative counterpart also exists. We will then remember the largest of these positive numbers.

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

Look at the first number in the list.
Check if its negative version is also in the list.
If both the number and its negative version are in the list, remember that number.
Move on to the next number in the list and repeat the process.
If the new number and its negative are in the list and the new number is larger than the one you remembered, then replace the remembered number with this larger number.
Keep doing this until you have checked every number in the list.
The number you have remembered at the end is the largest positive integer that exists with its negative in the list.

Code Implementation

def find_largest_positive_with_negative(numbers):
    largest_positive_found = -1

    for current_number in numbers:
        # Only process if the current number is positive.
        if current_number > 0:

            negative_counterpart = -current_number
            # Check if the negative counterpart exists in the list.
            if negative_counterpart in numbers:

                # Update the largest positive number if needed.
                if current_number > largest_positive_found:
                    largest_positive_found = current_number

    return largest_positive_found

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the input array of size n. For each number, it searches the same array again to find its negative counterpart. Thus, for each of the n elements, we potentially perform another n lookups. Therefore, the total operations are approximately n * n, resulting in a time complexity of O(n²).

Space Complexity

O(1) – The algorithm uses only a single variable to remember the largest positive number found so far. No additional data structures like arrays, hash maps, or lists are used to store intermediate results. Therefore, the auxiliary space required remains constant, irrespective of the input list's size N, making the space complexity O(1).

Optimal Solution

Approach

The goal is to find the largest positive number that also has its negative counterpart in the list. We want to avoid checking every single possible number by focusing on finding the biggest positive numbers first and quickly checking if their negative exists. This approach allows us to stop as soon as we find the answer.

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

First, organize the numbers in the list from largest to smallest.
Then, go through the list, checking each positive number one by one, starting with the largest.
For each positive number, quickly see if its negative version is also present in the list.
If both the positive number and its negative are in the list, you've found the answer! Since you started with the largest positive number, this will be the biggest one that meets the requirement. Stop and return this number.
If you go through the entire list and don't find a matching negative for any positive number, that means there isn't one, so the answer is that no such number exists.

Code Implementation

def find_largest_positive_with_negative(numbers):
    numbers.sort(reverse=True)

    number_set = set(numbers)

    for number in numbers:
        # Only process positive numbers
        if number > 0:

            negative_number = -number

            # Check if the negative counterpart exists
            if negative_number in number_set:
                return number

    # No such number exists
    return -1

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation impacting time complexity is the initial sorting of the input array of size n, which typically takes O(n log n) time using efficient algorithms like merge sort or quicksort. After sorting, we iterate through the array, performing a constant-time lookup (on average, using a hash set) for each positive number to check for its negative counterpart. Thus, after sorting, the lookup becomes O(n), but it is dominated by the O(n log n) sorting time, so the overall time complexity is O(n log n).

Space Complexity

O(1) – The algorithm sorts the input list in place, which doesn't use auxiliary space. It then iterates through the sorted list, checking for the negative counterpart. This search does not involve any extra data structures like hash maps or sets. Therefore, only a few variables for indexing are used, leading to constant auxiliary space regardless of the input size N.

Edge Cases

Case	How to Handle
Empty or null input array	Return -1 immediately as no positive integer K can be found in an empty array.
Array with only one element	Return -1 since we need both K and -K, requiring at least two elements.
Array contains only positive numbers	Return -1 since no negative counterpart exists for any positive number.
Array contains only negative numbers	Return -1 since no positive number exists.
Array contains zero	Zero does not contribute to finding a positive integer K and its negative -K, so it's ignored.
Array contains duplicates of K and -K	The algorithm should correctly identify K as a valid solution, even with duplicates of K and -K present.
Large input array with potential integer overflow during calculations	Use appropriate data types (e.g., long) or avoid calculations that could lead to overflow; if overflow occurs, catch the exception and handle it gracefully, returning -1 if necessary.
No valid solution exists	Return -1 when no integer K and its negative -K are found in the array after iterating through all the numbers.

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 are the constraints on the size of the input array `nums`?
What is the range of values for the integers within the input array `nums`?
If multiple positive integers `K` satisfy the condition (both `K` and `-K` exist), should I return the largest one, or is any valid `K` acceptable?
Are duplicate numbers allowed in the array? If so, how should duplicates affect the identification of `K`?
If the input array `nums` is empty, what should I return?

Brute Force Solution

Approach

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

Look at the first number in the list.
Check if its negative version is also in the list.
If both the number and its negative version are in the list, remember that number.
Move on to the next number in the list and repeat the process.
If the new number and its negative are in the list and the new number is larger than the one you remembered, then replace the remembered number with this larger number.
Keep doing this until you have checked every number in the list.
The number you have remembered at the end is the largest positive integer that exists with its negative in the list.

Code Implementation

def find_largest_positive_with_negative(numbers):
    largest_positive_found = -1

    for current_number in numbers:
        # Only process if the current number is positive.
        if current_number > 0:

            negative_counterpart = -current_number
            # Check if the negative counterpart exists in the list.
            if negative_counterpart in numbers:

                # Update the largest positive number if needed.
                if current_number > largest_positive_found:
                    largest_positive_found = current_number

    return largest_positive_found

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, organize the numbers in the list from largest to smallest.
Then, go through the list, checking each positive number one by one, starting with the largest.
For each positive number, quickly see if its negative version is also present in the list.
If both the positive number and its negative are in the list, you've found the answer! Since you started with the largest positive number, this will be the biggest one that meets the requirement. Stop and return this number.
If you go through the entire list and don't find a matching negative for any positive number, that means there isn't one, so the answer is that no such number exists.

Code Implementation

def find_largest_positive_with_negative(numbers):
    numbers.sort(reverse=True)

    number_set = set(numbers)

    for number in numbers:
        # Only process positive numbers
        if number > 0:

            negative_number = -number

            # Check if the negative counterpart exists
            if negative_number in number_set:
                return number

    # No such number exists
    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return -1 immediately as no positive integer K can be found in an empty array.
Array with only one element	Return -1 since we need both K and -K, requiring at least two elements.
Array contains only positive numbers	Return -1 since no negative counterpart exists for any positive number.
Array contains only negative numbers	Return -1 since no positive number exists.
Array contains zero	Zero does not contribute to finding a positive integer K and its negative -K, so it's ignored.
Array contains duplicates of K and -K	The algorithm should correctly identify K as a valid solution, even with duplicates of K and -K present.
Large input array with potential integer overflow during calculations	Use appropriate data types (e.g., long) or avoid calculations that could lead to overflow; if overflow occurs, catch the exception and handle it gracefully, returning -1 if necessary.
No valid solution exists	Return -1 when no integer K and its negative -K are found in the array after iterating through all the numbers.