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.
LeetCode Solutions1 <= n <= 1000-105 <= nums[i] <= 105The algorithm iterates through the array once, so the time complexity is linear in the size of the input array.
The algorithm uses a constant amount of extra space to store the closest number, regardless of the input size.
The algorithm iterates through the array once, keeping track of the closest number to zero found so far. For each number, it compares its absolute value to the absolute value of the closest number. If it's closer to zero, it updates the closest number. If it's equally close to zero but has a larger value, it also updates the closest number. This ensures that in case of a tie (e.g., -1 and 1), the larger value (1) is returned.
The algorithm iterates through the array twice in the worst case: once to find the closest number and once to check if a negative number with the same absolute value exists. Since both iterations are linear, the overall time complexity is .
The algorithm uses a constant amount of extra space to store temporary variables, regardless of the input size.
This approach first finds the number closest to zero in a single pass, then checks if there's a negative number with the same absolute value in the array. If such a number exists, it returns the positive version of that number. Otherwise, it returns the closest number found. This ensures that if there are two numbers equally close to zero (e.g., -1 and 1), the larger value (1) is returned.
| Approach | Rating | Time Complexity | Space Complexity | Advantages | Disadvantages |
|---|---|---|---|---|---|
| Single-pass with Tie-breaking | Handles tie-breaking inline during the scan | Slightly more complex condition checks | |||
| Linear Scan with Post-processing | Clean separation of concerns — find closest first, then handle ties | May iterate the array twice in worst case (still ) |
The optimal approach for this problem is Solution 2: Linear Scan with Post-processing, which achieves time complexity and space complexity. It cleanly separates the logic into two steps: first finding the closest number, then handling the tie-breaking case where a negative number's positive counterpart exists in the array.
class Solution: def findClosestNumber(self, nums: List[int]) -> int: closest = nums[0]
for i in range(1, len(nums)): # Check if the current number is closer to zero than the closest number found so far if abs(nums[i]) < abs(closest): closest = nums[i] elif abs(nums[i]) == abs(closest) and nums[i] > closest: # If the current number is equally close to zero as the closest number, but has a larger value, update closest closest = nums[i]
return closestclass Solution: def findClosestNumber(self, nums: List[int]) -> int: closest = nums[0]
for i in range(1, len(nums)): # Check if the current number is closer to zero than the closest number found so far if abs(nums[i]) < abs(closest): closest = nums[i]
# Check if the closest number is negative and its absolute value exists in the array if closest < 0 and abs(closest) in nums: return abs(closest) else: return closest