Largest Positive Integer That Exists With Its Negative

class Solution {
public:
    int maximumK(vector<int>& values) {
        int maxK = -1;
        bitset<2048> observed;
    
        for (int val : values) {
            int valAbs = abs(val);
            if (valAbs > maxK && observed[-val + 1024])
                maxK = valAbs;
            observed[val + 1024] = true;
        }
    
        return maxK;
    }
};

This solution defines a function maximumK that determines the largest integer k for which both k and -k exist in a given vector of integers named values. The approach utilizes a bitset of size 2048 to efficiently track which values (and their negative counterparts) exist in the vector.

• The bitset, named observed, is initialized with a size of 2048, allowing the tracking of integers and their negatives within an assumed reasonable range by shifting the index by 1024. This ensures indices remain positive within the bitset.
• For each integer val in the vector values, calculate valAbs, the absolute value of val.
• If valAbs is greater than the current maxK and the bit corresponding to -val + 1024 is set in observed (indicating both val and -val have been observed so far), then update maxK to valAbs.
• The bitset index for the current val is then set to true (observed[val + 1024] = true).
• After processing all elements in the vector, maxK is returned. If no such integer k exists, the function returns -1.

This approach is effective in solving the problem as it operates in linear time, thanks to the O(1) complexity of bitset operations and the single pass through the vector. Thus, maximumK competently identifies the maximum k that satisfies the conditions, in an optimal runtime.

class Solution {
    public int findMaximumK(int[] numbers) {
        int maxK = -1;
        BitSet observed = new BitSet(2048);
    
        for (int number : numbers) {
            int absoluteValue = Math.abs(number);
            if (absoluteValue > maxK && observed.get(-number + 1024))
                maxK = absoluteValue;
            observed.set(number + 1024);
        }
    
        return maxK;
    }
}

To solve the problem of finding the largest positive integer that exists with its negative in an array, you utilize the BitSet data structure in Java. This approach effectively tracks the existence of integers within the provided array, optimizing the search for the maximum integer k such that both k and -k are present in the array.

• Initialize maxK to -1, which will store the maximum integer found that meets the condition.
• Create BitSet observed with a size of 2048 to accommodate the range of possible values encountered in the array, considering positive and negative shifts.
• Iterate through each integer in the given array:
  • Compute the absolute value of the current number.
  • Check if the set contains the index corresponding to the negative of the current number (considering an offset of 1024 for actual 0 index). If both the number and its negative are observed, update maxK if the absolute value is larger than the current maxK.
  • Add the current number to the BitSet with an appropriate offset to handle negative values.

This method efficiently finds the largest integer k such that both k and -k are present, and returns it. If no such integer exists, the result is -1.

class Solution:
    def maximumK(self, numbers: List[int]) -> int:
        maximum_value = -1
        tracked_numbers = set()
    
        for value in numbers:
            abs_value = abs(value)
    
            # Check if current absolute value is greater than the stored value
            # and its opposite has been encountered
            if abs_value > maximum_value and -value + 1024 in tracked_numbers:
                maximum_value = abs_value
            # Add the current value adjusted by 1024 to the set
            tracked_numbers.add(value + 1024)
    
        return maximum_value

The provided Python solution determines the largest positive integer from a list that also has its negative present in the same list.

• The function maximumK expects an integer list numbers.
• It initializes maximum_value to -1 and creates an empty set tracked_numbers to track the adjusted values.
• The solution iterates through the list and for each value, calculates its absolute value abs_value.
• It checks if abs_value is greater than maximum_value and if the negative of the current value adjusted by 1024 exists in tracked_numbers. If both conditions are met, it updates maximum_value to the abs_value.
• After checking conditions, it adds the current value adjusted by 1024 into the tracked_numbers set.
• Finally, the function returns maximum_value, which represents the largest integer that and its negative are present in the list, or -1 if no such number exists.

The offset value of 1024 is used to handle negative index issues by ensuring all values are adjusted to a positive index in the set. This method efficiently finds the desired integer with a time complexity of O(n), where n is the number of elements in the provided list.