Leetcode 2441. Largest Positive Integer That Exists With Its Negative

Problem Description

#

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:

• Input: nums = [-1, 10, 6, 7, -7, 1]
• Output: 7
• Explanation: Both 1 and 7 have their corresponding negative numbers in the array. 7 is the largest.

Solution Approach

#

General Approach

#

Pass over the array, storing the fact we have seen that item. If the number’s negative has been seen before, then update the new maximum value.

Optimisations

#

The constraints only allow a small range of possible values:

$-1000 <= \text{nums[i]} <= 1000$

Therefore, we can use a static data structure, like an array, and store for every possible number whether we have seen it.

Since we only need to store true/false for each number to represent whether it has been seen before, we can use a bitset for space efficiency.

Given the smallest possible value is -1000, this will be index 0, and so to get the index of a number you add 1000.

Example

#

1. we see the number 47
   • seen[1000-47]==1 is checked and found false
   • so seen[1047] is set to 1
2. Later, the number -47 is seen.
   • seen[1000 -(-47)]==1 is checked and found true
   • |-47| is compared to the current maximum number

Complexity

#

Time complexity: O(n)

Space complexity: O(n)

Code

#

class Solution {
public:
    int findMaxK(const vector<int>& nums) {
        // indexes 1001-2000 represent positives. 0-999 are negatives
        bitset<2001> nums_bitset; 
        int ans = -1;
        for(const int& num : nums){
            if(nums_bitset[1000-num]==1){
                ans = max(ans, abs(num));
            }
            else{
                nums_bitset[1000+num] = 1;
            }
        }
        return ans;
    }
};