Two Liquids Closest to Zero
InterviewTime limit1sMemory limit128 MB
Given a sorted array, find two distinct numbers whose sum is closest to zero using a two-pointer sweep.
- Level
Medium4 of 10
- Topics
- Two pointers, Array, Greedy
- Solved
- No attempts yet
Problem
A science laboratory has many acidic and alkaline liquids. Each liquid has one integer that represents its property. An acidic liquid has a positive property value from 1 to 1,000,000,000, and an alkaline liquid has a negative property value from -1 to -1,000,000,000.
When two different liquids of equal amount are mixed, the property value of the mixture is the sum of the two selected values. The laboratory wants to choose two different liquids so that the mixture's value is as close to 0 as possible.
For example, if the property values are [-99, -2, -1, 4, 98], mixing the liquids with values -99 and 98 gives a mixture value of -1, which is closest to 0. In some cases, the best pair may consist of two acidic liquids or two alkaline liquids.
Given the property values in increasing order, write a program that finds two different liquids whose sum is closest to 0.
Input
The first line contains the number of liquids N. N is an integer between 2 and 100,000, inclusive.
The second line contains N distinct integers in increasing order, representing the property values of the liquids. Each value is between -1,000,000,000 and 1,000,000,000, inclusive. The input may contain only acidic liquids or only alkaline liquids.
Output
Print the property values of two different liquids whose sum is closest to 0 on one line. Print the two values in increasing order.
If multiple pairs satisfy the condition, any one of them may be printed.