Scale Engineer

Find Closest Number to Zero

Easy
#2039Time: 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.1 company
Data structures
Array
Companies
Tiger Analytics

Prompt

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 int array to an Integer array or a Stream to allow for custom object sorting.\n- Define a custom Comparator to 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:\n

java\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}\n
\nA more concise version using Java Streams:\n
java\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.

Solutions

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 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.

← Previous

Previous problem

Next →

Next problem