1. Overview
In this tutorial, we’ll delve into the problem of finding the closest number to zero within a Java array. For example, given the array, [1, -3, 2, -2, 4], the number closest to zero is 1. We’ll explore various techniques to efficiently find this number and enhance our problem-solving repertoire.
2. Approaches to Find the Closest Number to Zero
We’ll discuss several approaches, each with advantages and trade-offs. First, we’ll look at a brute force method, followed by an optimized approach using sorting and binary search, and finally, an alternative technique utilizing a priority queue.
2.1. The Brute Force Approach
This method involves a straightforward iteration through the array, calculating the absolute difference between each element and zero, and keeping track of the minimum difference encountered so far. If two numbers have the same absolute difference from zero, the method prioritizes the positive number to ensure a consistent and predictable result.
Let’s begin with an implementation:
public static int findClosestToZero(int[] arr) throws IllegalAccessException {
if (arr == null || arr.length == 0) {
throw new IllegalAccessException("Array must not be null or Empty");
}
int closest = arr[0];
for (int i = 1; i < arr.length; i++) {
if ((Math.abs(arr[i]) < Math.abs(closest)) ||
((Math.abs(arr[i]) == Math.abs(closest)) && (arr[i] > closest))) {
closest = arr[i];
}
}
return closest;
}
This approach provides a basic yet effective way to find the element closest to zero in an array of integers. Its time complexity is O(n), making it the most efficient for this problem. Let’s illustrate this with a test:
@Test
void whenFindingClosestToZeroWithBruteForce_thenResultShouldBeCorrect()
throws IllegalAccessException {
int[] arr = {1, 60, -10, 70, -80, 85};
assertEquals(1, BruteForce.findClosestToZero(arr));
}
2.2. Approach Using Sorting and Binary Search
This approach begins by sorting the array, simplifying the problem by arranging elements in ascending order of their absolute values. After sorting, a binary search algorithm is applied to efficiently locate the element closest to zero. After sorting, a binary search algorithm is applied to efficiently locate the element closest to zero. It is important to note that while binary search is efficient with a time complexity of O(log n), the sorting step adds O(n log n) complexity, making the overall time complexity O(n log n).
Let’s look at the implementation:
public static int findClosestToZero(int[] arr) {
if (arr == null || arr.length == 0) {
throw new IllegalArgumentException("Array must not be null or Empty");
}
Arrays.sort(arr);
int closestNumber = arr[0];
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (Math.abs(arr[mid]) < Math.abs(closestNumber)) {
closestNumber = arr[mid];
}
if (arr[mid] < 0) {
left = mid + 1;
} else if (arr[mid] > 0) {
right = mid - 1;
} else {
return arr[mid];
}
}
return closestNumber;
}
This implementation sorts the input array and then applies a binary search to check the middle of the current search range, narrowing it down to find the number with the smallest absolute value. Let’s validate this with a test:
@Test
void whenFindingClosestToZeroWithBruteForce_thenResultShouldBeCorrect() throws IllegalAccessException {
int[] arr = {1, 60, -10, 70, -80, 85};
assertEquals(1, SortingAndBinarySearch.findClosestToZero(arr));
}
For the array arr, the algorithm first sorts it in ascending order, thus [-80, -10, 1, 60, 70, 85]. The method initializes closestNumber to the first element, -80, and iterates using binary search. It updates closestNumber to 1 after finding that 1 is closer to zero than other elements from the first iteration. The first iteration also produces this sub array from the original array, [-80, -10, 1]. The binary search checks middle elements and adjusts the search range until it exits, confirming 1 as the closest to zero.
2.3. Approach Using Priority Queue
An alternative technique involves utilizing a priority queue to efficiently find the closest number to zero without sorting the entire array. It finds the closest number to zero by adding each number to the queue and keeping only the smallest number based on its absolute value.
Let’s implement this approach in Java:
public static int findClosestToZeroWithPriorityQueue(int[] arr, int k) {
if (arr == null || arr.length == 0 || k <= 0) {
throw new IllegalArgumentException("Invalid input");
}
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> Math.abs(b) - Math.abs(a));
for (int num : arr) {
pq.offer(num);
if (pq.size() > k) {
pq.poll();
}
}
return pq.peek();
}
The comparator Math.abs(b) – Math.abs(a) ensures that the priority queue orders elements based on their absolute values, with the farthest from zero having the lowest priority. As we iterate through the array, each element is added to the priority queue. If the size of the queue exceeds k, the element that is farthest from zero is removed, ensuring the queue maintains only the kth closest numbers to zero. Finally, pq.peek() returns the element that is closest to zero.
Let’s test it:
@Test
void whenFindingClosestToZeroWithBruteForce_thenResultShouldBeCorrect()
throws IllegalAccessException {
int[] arr = {1, 60, -10, 70, -80, 85};
assertEquals(1, PriorityQueueToZero.findClosestToZeroWithPriorityQueue(arr, 1));
}
For this test, the priority queue is initialized to hold only one element, representing the closest number to zero. The algorithm iterates through the array [1, 60, -10, 70, -80, 85], processing each element sequentially. Initially, 1 is added to the queue as it’s empty. As 60 is farther from zero compared to 1, it’s not added. When -10 is encountered, it’s not added because 1 is closer to zero in terms of absolute value. Subsequent elements 70, -80, and 85 are all farther from zero compared to -10, so none of them are added to the queue. After processing all elements, the queue retains 1 as the closest element to zero.
3. Comparison of Approaches
While all three approaches aim to find the closest number to zero within a Java array, they exhibit different characteristics.
- Brute force approach: although simple and the most efficient for solving this problem, it becomes increasingly inefficient for when multiple queries are required.
- Optimized approach with sorting and binary search: it offers better performance for larger arrays, but with a time complexity of O(n log n). Also, sorting may not be feasible in memory-constrained scenarios.
- Priority queue approach: it strikes a balance between simplicity and performance, making it suitable for scenarios where finding a subset of closest numbers is sufficient and sorting the array isn’t feasible.
4. Conclusion
In this article, we’ve explored approaches to tackle the problem of finding the closest number to zero in a Java array.
Each method has its strengths and trade-offs, highlighting the importance of selecting the right algorithm based on specific requirements.
The code used in this tutorial is available over on GitHub.