Largest Positive Integer That Exists With Its Negative

Largest Positive Integer That Exists With Its Negative

1. What is this problem about?

The Largest Positive Integer That Exists With Its Negative coding problem gives you an array of integers that does not contain zeros. You need to find the largest positive integer k such that both k and -k are present in the array. If no such integer exists, the function should return -1.

2. Why is this asked in interviews?

This "Easy" level question is popular at Microsoft and Amazon because it offers multiple ways to solve it, allowing interviewers to judge a candidate's ability to choose the most appropriate data structure. Whether you use a Hash Set, Sorting, or Two Pointers, the problem reveals your understanding of time-space trade-offs. It's a quick way to gauge basic coding fluency and efficiency.

3. Algorithmic pattern used

This problem can be solved using several patterns: Hash Table, Sorting, or Two Pointers interview pattern. The Hash Table approach involves storing all numbers in a set for O(1) lookups. Then, iterate through the set to find the maximum k where -k is also in the set. Alternatively, you can sort the array and use two pointers (one at each end) to find the largest matching pair.

4. Example explanation

Array: [-1, 10, 6, 7, -7, 1]. Method: Hash Set.

1. Put everything in a set: {-1, 1, 6, 7, -7, 10}.
2. Check each positive number:
   • Is 10's negative (-10) in set? No.
   • Is 7's negative (-7) in set? Yes! (Update max = 7).
   • Is 6's negative (-6) in set? No.
   • Is 1's negative (-1) in set? Yes. (1 < 7, so max stays 7). Final result: 7.

5. Common mistakes candidates make

The most common mistake is not keeping track of the "largest" value and simply returning the first pair found. Another error is not handling the case where no such pair exists, which should return -1. Some candidates might also use a nested loop, resulting in O(N²) complexity, which is unnecessary when O(N) is achievable.

6. Interview preparation tip

For "Hash Table, Two Pointers interview pattern" questions, always mention the trade-off. A Hash Set gives O(N) time and O(N) space, while Sorting + Two Pointers gives O(N log N) time but O(1) space. Showing you understand these nuances is what distinguishes a senior candidate.