algoadvance

Leetcode 2441. Largest Positive Integer That Exists With Its Negative

Problem Statement:

Given an integer array nums that does not contain any zero, find the largest positive integer k such that -k is also in nums. If there is no such integer, return -1.

Clarifying Questions:

  1. Will the array always contain at least one element?
    • Yes, the array will contain at least one element.
  2. Are there any constraints on the size of the array or the integer values?
    • The problem does not explicitly mention constraints, so we’ll assume typical constraints for such problems on LeetCode (e.g., 1 <= nums.length <= 10^4 and -10^5 <= nums[i] <= 10^5).
  3. Is the array sorted?
    • No, the array is not necessarily sorted.

Strategy:

  1. Use a Hash Set: This will allow O(1) average-time complexity for both insertions and lookups.
  2. Iterate Through the Array and Populate the Set: As we iterate through the array, keep track of the largest k for which both k and -k exist in the set.

Code:

#include <vector>
#include <unordered_set>
#include <algorithm>

int findMaxK(std::vector<int>& nums) {
    std::unordered_set<int> numSet;
    int largestK = -1;

    for (int num : nums) {
        numSet.insert(num);
    }

    for (int num : nums) {
        if (num > 0 && numSet.find(-num) != numSet.end()) {
            largestK = std::max(largestK, num);
        }
    }

    return largestK;
}

Explanation:

  1. Data Structure: The unordered set (numSet) is used to store all elements from the array. This allows us to quickly check the presence of -k.
  2. Two-Pass Approach:
    • First Pass: Populate the set with all elements for quick lookup.
    • Second Pass: Iterate through the array. For each positive integer k, check if -k exists in the set. Keep track of the maximum k found.

Time Complexity:

This approach ensures that we efficiently find the largest integer k such that both k and -k exist in the array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI