Largest Positive Integer That Exists With Its Negative Solution
Largest Positive Integer That Exists With Its Negative solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Largest Positive Integer That Exists With Its Negative is an easy coding problem on arrays, hash table and two pointers, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Two Pointers
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums that does not contain 0, return the largest positive integer k such that -k also appears in the array.
If no such k exists, return -1.
Example 1
Input: nums = [-1,2,-3,3]
Output: 3
Explanation: 3 and -3 are both present.
Example 2
Input: nums = [-1,10,6,7,-7,1]
Output: 7
Explanation: Both 1/-1 and 7/-7 qualify; 7 is larger.
Example 3
Input: nums = [-10,8,6,7,-2,-3]
Output: -1
Constraints
1 <= nums.length <= 1000-1000 <= nums[i] <= 1000nums[i] is never 0.
Hints for Largest Positive Integer That Exists With Its Negative
Hint 1
Put every value into a set first.
Hint 2
Then scan for positive values whose negation is also in the set.
Hint 3
Keep the largest such value;
-1if none.
How to solve Largest Positive Integer That Exists With Its Negative
Membership is the whole question, so a set turns it into a single linear scan.
Approach
- Insert every value into a set.
- Scan the array; for each positive
x, check whether-xis in the set. - Track the maximum qualifying
x, returning-1if none was found.
Why it works
The set makes each partner lookup O(1), so scanning once considers every candidate. Restricting to positive x avoids reporting the negative half of a pair.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Forgetting the
x > 0guard can return a negative value. - Sorting and two-pointering from both ends also works and uses O(1) extra space.
- The array never contains 0, so there is no
k = 0edge case.
Reference solution
Python
from typing import List
def findMaxK(nums: List[int]) -> int:
seen = set(nums)
best = -1
for x in nums:
if x > 0 and -x in seen and x > best:
best = x
return bestJava
public static int findMaxK(int[] nums) {
HashSet<Integer> seen = new HashSet<>();
for (int x : nums) seen.add(x);
int best = -1;
for (int x : nums) {
if (x > 0 && seen.contains(-x) && x > best) best = x;
}
return best;
}C++
int findMaxK(vector<int>& nums) {
unordered_set<int> seen(nums.begin(), nums.end());
int best = -1;
for (int x : nums) {
if (x > 0 && seen.count(-x) && x > best) best = x;
}
return best;
}JavaScript
var findMaxK = function(nums) {
const seen = {};
for (let i = 0; i < nums.length; i++) seen[String(nums[i])] = true;
let best = -1;
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
if (x > 0 && seen[String(-x)] === true && x > best) best = x;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets