Largest Positive Integer That Exists With Its Negative solution and explanation
Google
9 more videos on this problem
2441. Largest Positive Integer That Exists With Its Negative | Leetcode Weekly 315 | LeetCode 2441Bro Coders · 6:20 · 1K views
2441. Largest Positive Integer That Exists With Its Negative | 5 Ways | 2 Pointers | BitsetAryan Mittal · 19:00 · 1K views
2441. Largest Positive Integer That Exists With Its Negative (Leetcode Easy)Programming Live with Larry · 2:16 · 497 views
Beginners Solve 2441. Largest Positive Integer That Exists With Its NegativeHardworking Geniuses · 12:41 · 234 views
Leetcode 2441. Largest Positive Integer That Exists With Its NegativeElite Code · 3:59 · 201 views
Leetcode 2441: Largest Positive Integer That Exists With Its NegativeAlgorithms Casts · 5:04 · 184 views
2441. Largest Positive Integer That Exists With Its Negative with pythonArsalan Ahmed · 13:37 · 130 views
Largest Positive Integer That Exists With Its Negative - Leetcode 2441 - JavaCode With K5KC · 9:01 · 123 views
leetcode 2441. Largest Positive Integer That Exists With Its Negative - set ADT and checkCode-Yao · 4:51 · 101 views
Largest Positive Integer with Its Negative | LeetCode 2441 | Java Code | Developer CoderDeveloper Coder · 9:21 · 50 views
The problem
Given an integer array nums that does not contain any zeros, find the largest positive integer k such that -k also exists in the array.
Return the positive integer k. If there is no such integer, return -1.
Example 1:
Input: nums = [-1,2,-3,3] Output: 3 Explanation: 3 is the only valid k we can find in the array.
Example 2:
Input: nums = [-1,10,6,7,-7,1] Output: 7 Explanation: Both 1 and 7 have their corresponding negative values in the array. 7 has a larger value.
Example 3:
Input: nums = [-10,8,6,7,-2,-3] Output: -1 Explanation: There is no a single valid k, we return -1.
Constraints:
1 <= nums.length <= 1000-1000 <= nums[i] <= 1000nums[i] != 0
Approach overview
Problem Overview: You are given an integer array nums. The task is to find the largest positive integer k such that both k and -k appear in the array. If no such integer exists, return -1. The goal is to efficiently detect matching positive–negative pairs and track the maximum valid value.
Approach 1: Using HashSet for Fast Lookup (O(n) time, O(n) space)
This approach relies on a hash set for constant‑time lookups. First iterate through the array and insert each number into a HashSet. Then iterate again and check whether the opposite value (-num) exists in the set. Whenever both numbers exist, update the answer with the maximum positive value encountered. Because each lookup is O(1) on average, the full scan takes O(n) time while storing elements requires O(n) space. This is the most direct solution using a Hash Table and works well for unsorted input arrays.
Approach 2: Sorting to Simplify Pair Search (O(n log n) time, O(1) extra space)
Sorting the array groups negative and positive numbers in order, which makes it easier to find matching pairs. After sorting, use two pointers: one starting from the left (most negative) and one from the right (largest positive). Compare the absolute values of the numbers. If they match, you found a valid pair and can return that positive number immediately. If the absolute value on the left is larger, move the left pointer forward; otherwise move the right pointer backward. Sorting costs O(n log n), and the two‑pointer scan runs in O(n) time with O(1) additional space. This method combines Sorting with the Two Pointers technique.
Recommended for interviews: The hash set approach is typically expected because it achieves optimal O(n) time and is straightforward to implement. Interviewers want to see that you recognize the symmetric relationship between k and -k and use constant‑time lookups to detect pairs efficiently. The sorting approach is still valuable because it demonstrates comfort with pointer techniques and problem transformation, but it is slightly less optimal due to the sorting step.
Approach 1: Using HashSet for Fast Lookup
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.
def largest_equal_positive_negative(nums):
num_set = set()
largest = -1
for num in nums:
if -num in num_set:
largest = max(largest, abs(num))
num_set.add(num)
return largest
nums = [-1, 2, -3, 3]
print(largest_equal_positive_negative(nums)) # Output: 3import java.util.HashSet;
public class Solution {
public int largestEqualPositiveNegative(int[] nums) {
HashSet<Integer> numSet = new HashSet<>();
int largest = -1;
for (int num : nums) {
if (numSet.contains(-num)) {
largest = Math.max(largest, Math.abs(num));
}
numSet.add(num);
}
return largest;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {-1, 2, -3, 3};
System.out.println(solution.largestEqualPositiveNegative(nums)); // Output: 3
}
}#include <iostream>
#include <unordered_set>
#include <vector>
int largestEqualPositiveNegative(std::vector<int>& nums) {
std::unordered_set<int> numSet;
int largest = -1;
for (int num : nums) {
if (numSet.count(-num)) {
largest = std::max(largest, std::abs(num));
}
numSet.insert(num);
}
return largest;
}
int main() {
std::vector<int> nums = {-1, 2, -3, 3};
std::cout << largestEqualPositiveNegative(nums) << std::endl; // Output: 3
return 0;
}function largestEqualPositiveNegative(nums) {
const numSet = new Set();
let largest = -1;
for (const num of nums) {
if (numSet.has(-num)) {
largest = Math.max(largest, Math.abs(num));
}
numSet.add(num);
}
return largest;
}
const nums = [-1, 2, -3, 3];
console.log(largestEqualPositiveNegative(nums)); // Output: 3#include <stdio.h>
#include <stdlib.h>
int largestEqualPositiveNegative(int* nums, int numsSize) {
int hash[2001] = {0}; // To accommodate numbers from -1000 to 1000
int largest = -1;
for (int i = 0; i < numsSize; i++) {
int num = nums[i];
hash[num + 1000] = 1; // Using offset 1000 to handle negative indices
if (num > 0 && hash[-num + 1000]) {
if (num > largest) {
largest = num;
}
} else if (num < 0 && hash[-num + 1000]) {
if (-num > largest) {
largest = -num;
}
}
}
return largest;
}
int main() {
int nums[] = {-1, 2, -3, 3};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", largestEqualPositiveNegative(nums, size)); // Output: 3
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int LargestEqualPositiveNegative(int[] nums) {
HashSet<int> numSet = new HashSet<int>();
int largest = -1;
foreach (int num in nums) {
if (numSet.Contains(-num)) {
largest = Math.Max(largest, Math.Abs(num));
}
numSet.Add(num);
}
return largest;
}
public static void Main() {
Solution solution = new Solution();
int[] nums = {-1, 2, -3, 3};
Console.WriteLine(solution.LargestEqualPositiveNegative(nums)); // Output: 3
}
}Uses a set to track numbers. For each number, checks if its negative is in the set, updating the largest absolute value if a pair is found.
Time Complexity: O(n), as it traverses the list once.
Space Complexity: O(n), due to hash set storage.
Approach 2: Sorting to Simplify Pair Search
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.
def largest_equal_positive_negative(nums):
nums.sort()
left, right = 0, len(nums) - 1
largest = -1
while left < right:
if nums[left] + nums[right] == 0:
largest = nums[right]
left += 1
right -= 1
elif nums[left] + nums[right] < 0:
left += 1
else:
right -= 1
return largest
nums = [-1, 2, -3, 3]
print(largest_equal_positive_negative(nums)) # Output: 3import java.util.Arrays;
public class Solution {
public int largestEqualPositiveNegative(int[] nums) {
Arrays.sort(nums);
int left = 0, right = nums.length - 1, largest = -1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == 0) {
largest = nums[right];
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
return largest;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {-1, 2, -3, 3};
System.out.println(solution.largestEqualPositiveNegative(nums)); // Output: 3
}
}#include <iostream>
#include <vector>
#include <algorithm>
int largestEqualPositiveNegative(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
int left = 0, right = nums.size() - 1, largest = -1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == 0) {
largest = nums[right];
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
return largest;
}
int main() {
std::vector<int> nums = {-1, 2, -3, 3};
std::cout << largestEqualPositiveNegative(nums) << std::endl; // Output: 3
return 0;
}function largestEqualPositiveNegative(nums) {
nums.sort((a, b) => a - b);
let left = 0, right = nums.length - 1;
let largest = -1;
while (left < right) {
const sum = nums[left] + nums[right];
if (sum === 0) {
largest = nums[right];
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
return largest;
}
const nums = [-1, 2, -3, 3];
console.log(largestEqualPositiveNegative(nums)); // Output: 3#include <stdio.h>
#include <stdlib.h>
int compareInts(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int largestEqualPositiveNegative(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), compareInts);
int left = 0, right = numsSize - 1, largest = -1;
while (left < right) {
if (nums[left] + nums[right] == 0) {
largest = nums[right];
left++;
right--;
} else if (-nums[left] > nums[right]) {
left++;
} else {
right--;
}
}
return largest;
}
int main() {
int nums[] = {-1, 2, -3, 3};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", largestEqualPositiveNegative(nums, size)); // Output: 3
return 0;
}using System;
public class Solution {
public int LargestEqualPositiveNegative(int[] nums) {
Array.Sort(nums);
int left = 0, right = nums.Length - 1, largest = -1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == 0) {
largest = nums[right];
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
return largest;
}
public static void Main() {
Solution solution = new Solution();
int[] nums = {-1, 2, -3, 3};
Console.WriteLine(solution.LargestEqualPositiveNegative(nums)); // Output: 3
}
}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.
Time Complexity: O(n log n), for the initial array sort.
Space Complexity: O(1), not counting array input memory.
Approach 3: Hash Table
We can use a hash table s to record all elements that appear in the array, and a variable ans to record the maximum positive integer that satisfies the problem requirements, initially ans = -1.
Next, we traverse each element x in the hash table s. If -x exists in s, then we update ans = max(ans, x).
After the traversal ends, return ans.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array.
function findMaxK(nums: number[]): number {
let ans = -1;
const s = new Set(nums);
for (const x of s) {
if (s.has(-x)) {
ans = Math.max(ans, x);
}
}
return ans;
}func findMaxK(nums []int) int {
ans := -1
s := map[int]bool{}
for _, x := range nums {
s[x] = true
}
for x := range s {
if s[-x] && ans < x {
ans = x
}
}
return ans
}use std::collections::HashSet;
impl Solution {
pub fn find_max_k(nums: Vec<i32>) -> i32 {
let s = nums.into_iter().collect::<HashSet<i32>>();
let mut ans = -1;
for &x in s.iter() {
if s.contains(&-x) {
ans = ans.max(x);
}
}
ans
}
}Approach 4: Default Approach
use std::collections::HashSet;
impl Solution {
pub fn find_max_k(nums: Vec<i32>) -> i32 {
let mut ans = -1;
let mut h = HashSet::new();
for &n in &nums {
h.insert(n);
}
for &n in &nums {
if h.contains(&-n) && n > ans {
ans = n;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using HashSet for Fast Lookup | Time Complexity: O(n), as it traverses the list once. |
| Sorting to Simplify Pair Search | Time Complexity: O(n log n), for the initial array sort. |
| Hash Table | – |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashSet Fast Lookup | O(n) | O(n) | Best general solution when the array is unsorted and fast membership checks are needed |
| Sorting + Two Pointers | O(n log n) | O(1) | Useful when sorting is acceptable or when practicing two-pointer techniques |
Frequently asked questions
Is Largest Positive Integer That Exists With Its Negative easy or hard?
The problem is classified as Easy on LeetCode with a high acceptance rate around 75%. It mainly tests basic array traversal and HashSet usage rather than complex algorithms.
Largest Positive Integer That Exists With Its Negative Python/Java solution
Most implementations store numbers in a set and check for -num while iterating. Python typically uses a built-in set, while Java uses HashSet. Both achieve O(n) time and O(n) space complexity.
How to solve Largest Positive Integer That Exists With Its Negative in O(n)?
Store all numbers in a HashSet. Iterate through the array and check if the negative counterpart of each number exists in the set. Track the maximum positive value where both k and -k appear. Hash lookups make the overall complexity O(n).
What is the best approach for Largest Positive Integer That Exists With Its Negative?
The HashSet approach is the most efficient. Insert every number into a set, then check whether the opposite value (-num) exists. This allows constant-time lookups and solves the problem in O(n) time with O(n) space.
Is Largest Positive Integer That Exists With Its Negative asked at Google/Amazon/Meta?
Variants of this problem appear in interviews that test hash tables, array scanning, and pair detection logic. Companies such as Amazon, Google, and Meta commonly ask similar array and HashSet problems during early interview rounds.
What data structure is used in Largest Positive Integer That Exists With Its Negative?
A HashSet is the primary data structure used for the optimal solution. It provides O(1) average-time lookups, making it easy to check if both a number and its negative exist in the array.
What is the time complexity of Largest Positive Integer That Exists With Its Negative?
The optimal solution runs in O(n) time using a hash set to check whether both k and -k exist. A sorting-based alternative takes O(n log n) time due to the sorting step, followed by a linear scan.