2239. Find Closest Number to Zero

EasyArray
Leetcode Link

Problem Description

In this problem, you are provided with an integer array called nums, which has n number of elements. Your task is to find a number in nums that is closest to zero. If there is more than one such number, you will have to return the one with the largest value. Specifically, the closeness to zero is determined by the absolute value of the numbers, where the absolute value is the distance a number is from zero on the number line, without considering the direction (positive or negative).

Intuition

Approaching this problem, we should consider two key observations:

  1. We can determine how close a number is to zero by looking at its absolute value. The smaller the absolute value, the closer the number is to zero.

  2. In case of a tie—where two numbers are equally close to zero—we should return the larger number.

Given these observations, the solution involves iterating through each number in the array and tracking the one that is closest to zero. To keep track of the number closest to zero (let's call it ans), we also need to keep track of its absolute value (let's call it d, which stands for distance).

During each iteration, we check if the current number (x) has a smaller absolute value (y := abs(x)) than the smallest absolute we have seen so far (d). If it does, we update ans with x and d with y. In the case where y is equal to d, we perform an additional check: if x is greater than ans, we update ans to x because, as per the problem's requirement, we need to return the larger value in the event of a tie.

The solution initializes ans to zero and d with positive infinity (inf), which effectively means any number encountered first will replace these initial values. By iteratively updating our answers, once we go through the whole array, ans will hold the number closest to zero or the largest number in case of a tie.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which two pointer techniques do you use to check if a string is a palindrome?

Solution Approach

The implementation uses a simple linear scan algorithm that iterates through all the elements in the given integer array nums. It does not rely on any complex data structures and only requires a couple of variables to keep track of the state as it processes the array. The pattern used is straightforward and only requires basic conditional logic.

Here's a breakdown of the solution approach:

  1. Initialize ans to 0 and d to positive infinity (inf). These variables are used to store the closest number to zero (ans) and its absolute value (d), respectively.

  2. Iterate over each number x in the array nums.

  3. In each iteration, calculate the absolute value of the current number and store it in a temporary variable y using the expression y := abs(x).

  4. Compare the absolute value y with the current minimum distance d.

  5. If y is less than d, it means the current number x is closer to zero than any previous number we've encountered. So, update ans to x and d to y.

  6. If y is equal to d, it means there is a tie. In this case, check if the current number x is greater than ans. If x is greater, it means we have found a larger number that is equally close to zero, so update ans to x. This step ensures that in the event of a tie, the larger number is chosen.

  7. Continue this process until the loop has finished iterating through all the elements.

  8. Return the value of ans as it now contains the number closest to zero (or the largest number in case of a tie).

The simplicity of the algorithm makes it efficient—it runs in O(n) time, where n is the length of the array since it requires only one pass through the array. It has O(1) space complexity as it only uses a fixed amount of extra space regardless of the input size.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is a min heap?

Example Walkthrough

Suppose we have the following array nums: [3, -7, 2, 5, -2, 4]. Let's go through the solution step by step:

  1. We begin by initializing our answer ans to 0 and the minimum distance d to positive infinity.

  2. Starting with the first number in our array, 3, we calculate its absolute value which is also 3. Now, we compare this with d. Since 3 is less than positive infinity, we update ans to 3 and d to 3.

  3. We then move to the next number, which is -7. Its absolute value is 7. This is greater than our current minimum distance d of 3, so we do nothing.

  4. The next number is 2. Its absolute value is smaller than our current d. So we update ans to 2 and d to 2.

  5. We now consider 5. Its absolute value is greater than d, so, again, we do nothing.

  6. Next is -2. Its absolute value is the same as our current d. However, -2 is not greater than our current ans of 2, so we do not update ans.

  7. Finally, we consider 4. Its absolute value is greater than d, so there is no change to ans or d.

After scanning through all the elements in the array, we find that the number in nums closest to zero is 2, and that's what we return.

Here, step 6 is particularly important to note; even though -2 is as close to zero as 2, the problem statement asks us to prioritize the largest number in case of ties, which has been correctly maintained as 2 in ans.

Using the algorithm outlined, we have successfully found and would return the closest number to zero from the array.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findClosestNumber(self, nums: List[int]) -> int:
5        # Initialize the answer and the smallest absolute difference.
6        closest_number = 0
7        smallest_diff = float('inf')
8      
9        # Iterate through each number in the list.
10        for num in nums:
11            # Calculate the absolute difference of the current number.
12            current_diff = abs(num)
13          
14            # If the absolute difference is smaller than the smallest difference found so far,
15            # or if the absolute difference is equal but the number is greater (closer to zero),
16            # update the answer and the smallest difference.
17            if current_diff < smallest_diff or (current_diff == smallest_diff and num > closest_number):
18                closest_number = num
19                smallest_diff = current_diff
20      
21        # Return the number that is closest to zero.
22        return closest_number
23
1class Solution {
2    // Function to find the number closest to zero
3    public int findClosestNumber(int[] nums) {
4        int closestNumber = 0; // Stores the closest number to zero found so far
5        int minDistance = Integer.MAX_VALUE; // Initialize the minimum distance to the largest value possible
6
7        // Loop through each number in the array
8        for (int number : nums) {
9            // Calculate the absolute value of the current number
10            int absValue = Math.abs(number);
11
12            // Check if the absolute value is less than the currently found minimum distance
13            // Or if it is equal and the number is greater than the closest number found
14            if (absValue < minDistance || (absValue == minDistance && number > closestNumber)) {
15                closestNumber = number; // The current number is now the closest to zero
16                minDistance = absValue; // Update the minimum distance
17            }
18        }
19
20        // Return the number closest to zero found in the array
21        return closestNumber;
22    }
23}
24
1#include <vector>
2#include <climits> // For using INT_MAX
3
4class Solution {
5public:
6    // Function to find the closest number to zero in the given vector.
7    // In case of a tie, returns the number that is greater (more positive).
8    int findClosestNumber(vector<int>& nums) {
9        int closestNumber = 0; // This will hold the number closest to zero
10        int minDistance = INT_MAX; // This will hold the smallest distance from zero
11
12        // Iterate through each number in the vector
13        for (int number : nums) {
14            int distance = abs(number); // Find the absolute value to get the distance from zero
15          
16            // If the current number is closer to zero or it is the positive number in case of a tie
17            if (distance < minDistance || (distance == minDistance && number > closestNumber)) {
18                closestNumber = number; // Update the closest number
19                minDistance = distance; // Update the minimum distance
20            }
21        }
22      
23        // After the loop, return the number that is closest to zero
24        return closestNumber;
25    }
26};
27
1/**
2 * Finds the closest number to zero in the array. If there are two numbers with 
3 * the same distance from zero, the positive one will be prioritized.
4 * 
5 * @param {number[]} numbers The array of numbers to search through.
6 * @return {number} The number closest to zero.
7 */
8function findClosestNumber(numbers: number[]): number {
9    // Initialize answer and smallest difference 'delta'
10    // with a large number for starting comparisons.
11    let [closestNumber, smallestDelta] = [0, Number.MAX_SAFE_INTEGER];
12
13    // Iterate through each number in the array.
14    for (const num of numbers) {
15        // Calculate the absolute value of the current number.
16        const currentDelta = Math.abs(num);
17
18        // Check if the current number is closer to zero than the previous closest number,
19        // or if it's equally close to zero but positive.
20        if (currentDelta < smallestDelta || (currentDelta === smallestDelta && num > closestNumber)) {
21            // Update closest number and smallest difference.
22            [closestNumber, smallestDelta] = [num, currentDelta];
23        }
24    }
25
26    // Return the number closest to zero from the list.
27    return closestNumber;
28}
29
Not Sure What to Study? Take the 2-min Quiz：

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Time and Space Complexity

The code provided consists of a single loop that iterates over each element in the list nums. Inside this loop, we perform a constant number of operations: calculating the absolute value of the current element x, comparing it to the minimum distance found so far d, and possibly updating the answer ans and the distance d. These operations are constant time operations that don't depend on the size of the input list.

Thus, the time complexity of this loop is O(n), where n is the number of elements in the input list nums, since we have to look at each number exactly once to determine the answer.

In terms of space complexity, the code uses a fixed number of variables (ans and d) and does not utilize any additional data structures that scale with the size of the input. As a result, the space complexity is O(1), which means that it requires a constant amount of additional memory regardless of the size of the input list.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫