Sponsored
Sponsored
This approach utilizes a HashSet to keep track of the numbers we have encountered. As we iterate through the list, we check both the presence of a number and its negative in the HashSet. We update the largest number that satisfies the condition.
Time Complexity: O(n), since we iterate through the array once.
Space Complexity: O(1), since the hash set array size is always constant and independent of input size.
1#include <iostream>
2#include <unordered_set>
3#include <vector>
4
5int largestEqualPositiveNegative(std::vector<int>& nums) {
6 std::unordered_set<int> numSet;
7 int largest = -1;
8 for (int num : nums) {
9 if (numSet.count(-num)) {
10 largest = std::max(largest, std::abs(num));
11 }
12 numSet.insert(num);
13 }
14 return largest;
15}
16
17int main() {
18 std::vector<int> nums = {-1, 2, -3, 3};
19 std::cout << largestEqualPositiveNegative(nums) << std::endl; // Output: 3
20 return 0;
21}This solution uses an unordered_set to perform constant time checks for the existence of numbers. As we loop through the list, we check for each number if its negative is in the set and update the largest value accordingly.
In this approach, we first sort the array so that we can efficiently find pairs of positive and negative numbers. Once sorted, we use two pointers: one starting from the beginning (for negative numbers) and one from the end (for positive numbers) to find the largest integer pair where both a positive and its negative exist.
Time Complexity: O(n log n) for the sorting operation.
Space Complexity: O(1) additional space beyond input storing.
Implementing a sorting step allows us to use a two-pointer strategy for rapid scanning for valid number pairs, extracting their largest positive k value when found.