Largest Positive Integer That Exists With Its Negative - Leetcode Solution

Problem Statement: Given an array of integers, find the largest positive integer that exists with its negative.

Input: The input consists of an integer array nums[] of n integers (−1,000,000 ≤ nums[i] ≤ 1,000,000).

Output: The output is a single integer, which is the largest positive integer that exists with its negative.

Approach: The approach to solve this problem is to loop through the given array and check if there exists a negative number for each positive number in the array. If yes, then take the maximum of the absolute values of these numbers and store it in a variable. The final result will be the maximum of all such variables.

Algorithm:

1. Initialize a variable max_num to -1, which will store the maximum absolute value of the numbers.

2. Loop through the array nums[] from index 0 to n-1. For each i-th element, check if there exists a negative number for that element in the array. If yes, then store the maximum of the absolute values of these numbers in a variable temp.

3. If temp is greater than max_num, then update max_num to temp.

4. Return max_num.

Pseudo Code:

int max_num = -1;

for (int i = 0; i < n; i++) { if (nums[i] > 0 && find(nums.begin(), nums.end(), -nums[i]) != nums.end()) { int temp = max(nums[i], abs(-nums[i])); max_num = max(max_num, temp); } }

return max_num;

Time Complexity: The time complexity of this approach is O(n^2) because of the usage of find() function inside the loop. The find() function has a time complexity of O(n), which makes the overall time complexity O(n^2).

Space Complexity: The space complexity of this approach is O(1) because it does not use any extra space except for the max_num variable.

Implementation:

class Solution { public: int largestNumber(vector<int>& nums) { int max_num = -1;

    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] > 0 && find(nums.begin(), nums.end(), -nums[i]) != nums.end()) {
            int temp = max(nums[i], abs(-nums[i]));
            max_num = max(max_num, temp);
        }
    }

    return max_num;
}

};

The above implementation has been submitted and accepted on leetcode.

1