Jobs

Interviews

Discussions

Find Closest Number to Zero

Easy

Asked by:

More companies

13 views

Topics:

Arrays

Given an integer array nums of size n, return the number with the value closest to 0 in nums. If there are multiple answers, return the number with the largest value.

Example 1:

Input: nums = [-4,-2,1,4,8]
Output: 1
Explanation:
The distance from -4 to 0 is |-4| = 4.
The distance from -2 to 0 is |-2| = 2.
The distance from 1 to 0 is |1| = 1.
The distance from 4 to 0 is |4| = 4.
The distance from 8 to 0 is |8| = 8.
Thus, the closest number to 0 in the array is 1.

Example 2:

Input: nums = [2,-1,1]
Output: 1
Explanation: 1 and -1 are both the closest numbers to 0, so 1 being larger is returned.

Constraints:

1 <= n <= 1000
-10⁵ <= nums[i] <= 10⁵

Try coding it in LeetCode

Find Closest Number to Zero

Easy

Asked by:

13 views

Topics:

Arrays

Given an integer array nums of size n, return the number with the value closest to 0 in nums. If there are multiple answers, return the number with the largest value.

Example 1:

Input: nums = [-4,-2,1,4,8]
Output: 1
Explanation:
The distance from -4 to 0 is |-4| = 4.
The distance from -2 to 0 is |-2| = 2.
The distance from 1 to 0 is |1| = 1.
The distance from 4 to 0 is |4| = 4.
The distance from 8 to 0 is |8| = 8.
Thus, the closest number to 0 in the array is 1.

Example 2:

Input: nums = [2,-1,1]
Output: 1
Explanation: 1 and -1 are both the closest numbers to 0, so 1 being larger is returned.

Constraints:

1 <= n <= 1000
-10⁵ <= nums[i] <= 10⁵

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 range of values for integers in the `nums` array? Are there any constraints on the minimum or maximum possible value?
Can the input array `nums` be empty or null?
If there are multiple numbers equally close to zero, but some are positive and some are negative, should I always return the positive one, or is there another tie-breaker?
Is the input array guaranteed to contain at least one element?
Can the array contain floating point numbers, or is it strictly integers as the problem statement implies?

Brute Force Solution

Approach

The brute force approach to finding the number closest to zero involves checking every single number in the given set. We'll compare the distance of each number from zero to find the smallest distance.

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

Look at the first number in the collection.
Determine how far away it is from zero. We only care about the magnitude, not whether it's positive or negative.
Keep this distance in mind, along with the number itself.
Now, look at the next number.
Figure out how far this number is from zero as well.
Compare this new distance to the distance we stored earlier.
If the new distance is smaller, forget the old number and distance and remember the new number and distance.
If the new distance is the same as the old distance, compare the new number to the old number. Remember whichever number is positive.
Keep doing this for every number in the collection.
At the very end, the number you're remembering is the closest to zero.

Code Implementation

def find_closest_to_zero_brute_force(numbers):
    closest_number = numbers[0]
    smallest_distance = abs(numbers[0])

    for number in numbers:
        current_distance = abs(number)

        # Check if current distance is smaller
        if current_distance < smallest_distance:

            smallest_distance = current_distance
            closest_number = number

        # Handle the case where distances are equal
        elif current_distance == smallest_distance:

            # Prefer the positive number
            if number > closest_number:

                closest_number = number

    return closest_number

Big(O) Analysis

Time Complexity

O(n) – The provided algorithm iterates through the input array of size n exactly once. In each iteration, it performs a constant amount of work: calculating the absolute value of the current number, comparing it with the currently closest number's distance from zero, and potentially updating the closest number. Since the amount of work done per element is constant, the overall time complexity is directly proportional to the number of elements, n.

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. It stores only two variables: the closest number found so far and its corresponding distance from zero. The amount of memory used for these variables does not depend on the input size N, where N is the number of elements in the collection. Therefore, the space complexity is constant.

Optimal Solution

Approach

The fastest way to find the number closest to zero is to focus on finding the smallest positive and largest negative numbers. We only need to consider these two values and compare their distances to zero. This is much better than checking every number in the list.

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

First, find the smallest positive number from the list.
Next, find the largest negative number from the list.
Calculate how far each of these two numbers are from zero. In other words, find the absolute value of each number.
Compare the distances you calculated. If the positive number is closer to zero, that's your answer.
If the negative number is closer to zero, that's your answer.
If they are equally far away from zero, the positive number is the answer according to the problem statement.

Code Implementation

def find_closest_to_zero(numbers):
    smallest_positive = float('inf')
    largest_negative = float('-inf')

    for number in numbers:
        if number > 0:
            smallest_positive = min(smallest_positive, number)
        elif number < 0:
            largest_negative = max(largest_negative, number)

    # Handle the case where no positive or negative numbers exist
    if smallest_positive == float('inf') and largest_negative == float('-inf'):
        return 0
    elif smallest_positive == float('inf'):
        return largest_negative
    elif largest_negative == float('-inf'):
        return smallest_positive

    positive_distance = abs(smallest_positive)
    negative_distance = abs(largest_negative)

    # Need to compare the absolute values to find closest.
    if positive_distance < negative_distance:

        return smallest_positive

    # If distances are equal, positive number is returned per instructions
    else:

        return smallest_positive

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n once to find the smallest positive number. It then iterates through the array again, also of size n, to find the largest negative number. Finally, it performs a constant number of comparisons (absolute value calculations and distance comparison). Thus, the time complexity is dominated by the two linear traversals, resulting in O(n + n), which simplifies to O(n).

Space Complexity

O(1) – The algorithm stores the smallest positive number and the largest negative number. These are stored in constant space, independent of the size of the input array. No other auxiliary data structures like lists or hash maps are used, meaning the additional space required does not scale with the input size, N. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 or throw an exception, as the problem doesn't specify, but the solution must explicitly handle this case.
Array with only one element	Return that single element as it's trivially the closest to zero.
Array contains only zero	Return 0 directly, which is the closest number to zero.
Array contains both positive and negative numbers equidistant from zero, like [-1, 1, 2]	Prioritize returning the positive number as stated in the problem description.
Array contains duplicate numbers, some positive, some negative, e.g. [-2, -1, 1, 2]	Ensure the algorithm correctly identifies the closest, choosing positive if equally distant.
Array contains maximum and minimum integer values (Integer.MAX_VALUE, Integer.MIN_VALUE)	Consider potential overflow if calculating absolute values or distances, and use long if necessary.
Array with all negative numbers	The algorithm should still correctly identify the number closest to zero from the negative numbers.
Large input array (scalability)	A linear time solution (O(n)) is expected; ensure the algorithm doesn't have hidden quadratic complexity.

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 range of values for integers in the `nums` array? Are there any constraints on the minimum or maximum possible value?
Can the input array `nums` be empty or null?
If there are multiple numbers equally close to zero, but some are positive and some are negative, should I always return the positive one, or is there another tie-breaker?
Is the input array guaranteed to contain at least one element?
Can the array contain floating point numbers, or is it strictly integers as the problem statement implies?

Brute Force Solution

Approach

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

Look at the first number in the collection.
Determine how far away it is from zero. We only care about the magnitude, not whether it's positive or negative.
Keep this distance in mind, along with the number itself.
Now, look at the next number.
Figure out how far this number is from zero as well.
Compare this new distance to the distance we stored earlier.
If the new distance is smaller, forget the old number and distance and remember the new number and distance.
If the new distance is the same as the old distance, compare the new number to the old number. Remember whichever number is positive.
Keep doing this for every number in the collection.
At the very end, the number you're remembering is the closest to zero.

Code Implementation

def find_closest_to_zero_brute_force(numbers):
    closest_number = numbers[0]
    smallest_distance = abs(numbers[0])

    for number in numbers:
        current_distance = abs(number)

        # Check if current distance is smaller
        if current_distance < smallest_distance:

            smallest_distance = current_distance
            closest_number = number

        # Handle the case where distances are equal
        elif current_distance == smallest_distance:

            # Prefer the positive number
            if number > closest_number:

                closest_number = number

    return closest_number

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, find the smallest positive number from the list.
Next, find the largest negative number from the list.
Calculate how far each of these two numbers are from zero. In other words, find the absolute value of each number.
Compare the distances you calculated. If the positive number is closer to zero, that's your answer.
If the negative number is closer to zero, that's your answer.
If they are equally far away from zero, the positive number is the answer according to the problem statement.

Code Implementation

def find_closest_to_zero(numbers):
    smallest_positive = float('inf')
    largest_negative = float('-inf')

    for number in numbers:
        if number > 0:
            smallest_positive = min(smallest_positive, number)
        elif number < 0:
            largest_negative = max(largest_negative, number)

    # Handle the case where no positive or negative numbers exist
    if smallest_positive == float('inf') and largest_negative == float('-inf'):
        return 0
    elif smallest_positive == float('inf'):
        return largest_negative
    elif largest_negative == float('-inf'):
        return smallest_positive

    positive_distance = abs(smallest_positive)
    negative_distance = abs(largest_negative)

    # Need to compare the absolute values to find closest.
    if positive_distance < negative_distance:

        return smallest_positive

    # If distances are equal, positive number is returned per instructions
    else:

        return smallest_positive

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 or throw an exception, as the problem doesn't specify, but the solution must explicitly handle this case.
Array with only one element	Return that single element as it's trivially the closest to zero.
Array contains only zero	Return 0 directly, which is the closest number to zero.
Array contains both positive and negative numbers equidistant from zero, like [-1, 1, 2]	Prioritize returning the positive number as stated in the problem description.
Array contains duplicate numbers, some positive, some negative, e.g. [-2, -1, 1, 2]	Ensure the algorithm correctly identifies the closest, choosing positive if equally distant.
Array contains maximum and minimum integer values (Integer.MAX_VALUE, Integer.MIN_VALUE)	Consider potential overflow if calculating absolute values or distances, and use long if necessary.
Array with all negative numbers	The algorithm should still correctly identify the number closest to zero from the negative numbers.
Large input array (scalability)	A linear time solution (O(n)) is expected; ensure the algorithm doesn't have hidden quadratic complexity.