Find Closest Number to Zero
EasyPrompt
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-105 <= nums[i] <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves sorting the array based on a custom rule that directly aligns with the problem's conditions. We sort the numbers primarily by their distance from zero (absolute value) in ascending order. For numbers with the same distance, we sort them by their actual value in descending order. After sorting, the first element in the array will be the answer.
Algorithm
- Convert the primitive
intarray to anIntegerarray or aStreamto allow for custom object sorting.\n- Define a customComparatorto sort the numbers.\n- The comparator first compares two numbers based on their absolute values. The one with the smaller absolute value is considered "smaller".\n- If the absolute values are equal, the comparator then compares the numbers themselves in descending order. The larger number is considered "smaller" to place it earlier in the sorted sequence.\n- Sort the array/stream using this comparator.\n- The first element of the sorted collection is the result.
Walkthrough
The core idea is to define a sorting order that places the desired number at the very beginning of the array.\n\nThe sorting criteria are:\n1. Primary criterion: The absolute value of the number. A smaller absolute value means the number is closer to zero and should come first.\n2. Secondary criterion (for ties in absolute value): The actual value of the number. The problem requires the largest value in case of a tie, so we sort these numbers in descending order.\n\nBy applying this custom sort, the number that is closest to zero (and largest in case of a tie) will be moved to the first position of the array.\n\nHere is a Java implementation using a custom Comparator:\njava\nimport java.util.Arrays;\nimport java.util.Comparator;\n\nclass Solution {\n public int findClosestNumber(int[] nums) {\n // Convert int[] to Integer[] to use custom comparator with Arrays.sort\n Integer[] numsObj = new Integer[nums.length];\n for (int i = 0; i < nums.length; i++) {\n numsObj[i] = nums[i];\n }\n\n Arrays.sort(numsObj, new Comparator<Integer>() {\n @Override\n public int compare(Integer a, Integer b) {\n int absA = Math.abs(a);\n int absB = Math.abs(b);\n if (absA != absB) {\n return Integer.compare(absA, absB); // Sort by absolute value ascending\n } else {\n return Integer.compare(b, a); // If absolute values are equal, sort by value descending\n }\n }\n });\n\n return numsObj[0];\n }\n}\njava\nimport java.util.Arrays;\nimport java.util.Comparator;\n\nclass Solution {\n public int findClosestNumber(int[] nums) {\n return Arrays.stream(nums)\n .boxed()\n .min(Comparator.comparingInt(Math::abs)\n .thenComparing(Comparator.reverseOrder()))\n .get();\n }\n}\n
Complexity
Time
O(n log n), where n is the number of elements in the array. This is dominated by the sorting algorithm (`Arrays.sort` or `Stream.sorted`).
Space
O(n) in the worst case. This is required to store the `Integer` array when converting from a primitive `int[]`. If using streams, the space complexity can also be O(n) for intermediate storage. If the input were already an `Integer[]`, an in-place sort would have a space complexity of O(log n) for the recursion stack.
Trade-offs
Pros
The logic is concise and declarative, especially when using Java Streams.
It correctly handles all conditions of the problem within the sorting logic itself.
Cons
Less efficient than a single-pass approach due to the O(n log n) time complexity of sorting.
Requires extra space (O(n)) to convert the primitive array to an object array for sorting with a custom comparator.
This is the most efficient approach. We can find the closest number by iterating through the array just once. We maintain a variable to keep track of the closest number found so far and update it as we scan through the array based on the problem's criteria.
Algorithm
- Initialize a variable
closestNumwith the first number in the array andminDistwith its absolute value.\n- Iterate through the array from the second element to the end.\n- In each iteration, get the current numbernumand its absolute valuedist.\n- ComparedistwithminDist.\n- Ifdistis smaller thanminDist, updateminDisttodistandclosestNumtonum.\n- Ifdistis equal tominDist, updateclosestNumto the larger value between the currentclosestNumandnum.\n- After the loop finishes,closestNumholds the result.
Walkthrough
The idea is to iterate through the array while keeping track of the number that is currently the best candidate for the answer.\n\nWe initialize a variable, say closestNum, with the first element of the array. We also need to know its distance from zero, minDist.\n\nThen, we loop through the rest of the array. For each number num, we compare its distance to zero (Math.abs(num)) with minDist.\n\nThere are two conditions for updating our candidate:\n1. If Math.abs(num) is strictly less than minDist, it means num is a better candidate because it's closer to zero. We update closestNum to num and minDist to Math.abs(num).\n2. If Math.abs(num) is equal to minDist, we have a tie. The problem requires us to choose the larger value. So, we update closestNum to be the maximum of its current value and num.\n\nAfter checking all the numbers in the array, closestNum will hold the final answer.\n\nHere is the Java implementation:\njava\nclass Solution {\n public int findClosestNumber(int[] nums) {\n int closestNum = nums[0];\n int minDist = Math.abs(nums[0]);\n\n for (int i = 1; i < nums.length; i++) {\n int currentNum = nums[i];\n int currentDist = Math.abs(currentNum);\n\n if (currentDist < minDist) {\n minDist = currentDist;\n closestNum = currentNum;\n } else if (currentDist == minDist) {\n closestNum = Math.max(closestNum, currentNum);\n }\n }\n return closestNum;\n }\n}\n
Complexity
Time
O(n), where n is the number of elements in the array. We perform a single pass through the array.
Space
O(1), as we only use a constant amount of extra space for variables like `closestNum` and `minDist`.
Trade-offs
Pros
Optimal time complexity, making it the most efficient way to solve the problem.
Optimal space complexity, as it doesn't require any additional data structures that scale with the input size.
The logic is straightforward and easy to implement.
Cons
The logic is slightly more imperative compared to the declarative nature of the sorting approach with streams.
Solutions
Solution
class Solution: def findClosestNumber(self, nums: List[int]) -> int: ans, d = 0, inf for x in nums: if (y: = abs(x)) < d or (y == d and x > ans): ans, d = x, y return ansclass Solution {public int findClosestNumber(int[] nums) { int ans = 0, d = 1 << 30; for (int x : nums) { int y = Math.abs(x); if (y < d || (y == d && x > ans)) { ans = x; d = y; } } return ans; }}class Solution {public: int findClosestNumber(vector<int> &nums) { int ans = 0, d = 1 << 30; for (int x : nums) { int y = abs(x); if (y < d || (y == d && x > ans)) { ans = x; d = y; } } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.