LeetCode 2441. Largest Positive Integer That Exists With Its Negative Solution in Java, C++, Python & More | Explanation + Code

Description

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] <= 1000
• nums[i] != 0

Solutions

Solution 1: 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.

PythonJavaC++GoTypeScriptRust

class Solution: def findMaxK(self, nums: List[int]) -> int: s = set(nums) return max((x for x in s if -x in s), default=-1)(code-box)

class Solution { public int findMaxK(int[] nums) { int ans = -1; Set<Integer> s = new HashSet<>(); for (int x : nums) { s.add(x); } for (int x : s) { if (s.contains(-x)) { ans = Math.max(ans, x); } } return ans; } }(code-box)

class Solution { public: int findMaxK(vector<int>& nums) { unordered_set<int> s(nums.begin(), nums.end()); int ans = -1; for (int x : s) { if (s.count(-x)) { ans = max(ans, x); } } return ans; } };(code-box)

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 }(code-box)

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; }(code-box)

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 } }(code-box)

Solution 2

Rust

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 } }(code-box)