LC2441. Largest Positive Integer That Exists With Its Negative

Approach 1: Two-pointer

class Solution:
    def findMaxK(self, nums: List[int]) -> int:
        nums.sort()
        l, r = 0, len(nums) - 1
 
        while l < r and nums[l] < 0:
            if -nums[l] == nums[r]:
                return nums[r]
            
            if -nums[l] > nums[r]:
                l += 1
            else:
                r -= 1
        
        return -1
 

Complexity

Time: $O(nlogn)$
Space: $O(1)$

Approach 2: One-pass hash

class Solution:
    def findMaxK(self, nums: List[int]) -> int:
        seen = set()
 
        ans = -1
        for num in nums:
            if -num in seen and abs(num) > ans:
                ans = abs(num)
            
            seen.add(num)
 
        return ans

Complexity

Time: $O(n)$
Space: $O(n)$

Approach 3: BitSet

import kotlin.math.abs
 
class Solution {
    fun findMaxK(nums: IntArray): Int {
        var seen = BitSet(2048)
 
        var ans = -1
        for (num in nums) {
            if (seen.get(-num + 1024) && abs(num) > ans) {
                ans = abs(num)
            }
 
            seen.set(num + 1024, true)
        }
 
        return ans
    }
}

Time: $O(n)$
Space: $O(1)$ — Since fixed size bitset is used.

Other Languages