#2441

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Largest Positive Integer That Exists With Its Negative

Find the largest positive integer in an array such that its negative counterpart also exists.

Problem Statement

You are given an integer array nums that does not contain any zeros. Your task is to find the largest positive integer k such that its negative counterpart, -k, also exists in the array.

Return the positive integer k if it exists, or return -1 if no such integer can be found.

Examples

Example 1

Input: nums = [-1,2,-3,3]

Output: 3

3 is the only valid k we can find in the array.

Example 2

Input: nums = [-1,10,6,7,-7,1]

Output: 7

Both 1 and 7 have their corresponding negative values in the array. 7 has a larger value.

Example 3

Input: nums = [-10,8,6,7,-2,-3]

Output: -1

There is no a single valid k, we return -1.

Constraints

1 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
nums[i] != 0

Solution Approach

Array Scanning and Hash Lookup

Iterate through the array while using a hash table (or set) to track the values. For each positive number, check if its negative counterpart is present in the set. This allows quick lookups and ensures an O(n) time complexity.

Return the Largest Valid k

Track the largest k found while scanning the array. For every valid k (where -k is found), compare it with the previous largest k to ensure the largest one is returned.

Edge Case Handling

Handle cases where no valid k exists by returning -1. The solution must ensure the array is scanned fully, accounting for any possible negatives in the array.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(m)

The time complexity is O(n) because each element in the array is processed once, and hash lookups take constant time. The space complexity is O(m), where m is the number of unique elements in the array, as we store these in a hash set.

What Interviewers Usually Probe

Understanding of hash table usage and time complexity optimization.
Ability to handle edge cases such as no valid k or arrays with mixed signs.
Clear explanation of scanning and lookups as key components of the solution.

Common Pitfalls or Variants

Common pitfalls

Forgetting to account for the case where no valid k exists and returning -1.
Misunderstanding the problem by only focusing on positive integers without checking for the corresponding negative counterpart.
Overcomplicating the solution by using inefficient data structures or algorithms.

Follow-up variants

Consider variations with larger arrays, where the hash set implementation's efficiency becomes crucial.
Handle input with only negative numbers or only positive numbers.
Test with an array that has duplicates to see if they affect the output.

FAQ

What is the main approach to solving the 'Largest Positive Integer That Exists With Its Negative' problem?

The main approach involves scanning the array and using a hash table to check if the negative counterpart of each element exists, ensuring efficient lookup and identification of the largest valid k.

Why is the hash table used in this problem?

The hash table allows for O(1) lookups, making it efficient to check if an element's negative counterpart exists during the array scan.

What should be returned if no valid k exists?

If no valid k exists, the function should return -1.

How do we ensure that we return the largest k?

By comparing each valid k with the previously found largest k and updating the largest value when a new valid k is encountered.

How does the solution handle edge cases?

Edge cases such as arrays with no valid k or arrays with only negative or positive numbers are handled by returning -1 or skipping unnecessary checks.

terminal

Solution

Solution 1: Hash Table

We can use a hash table $s$ to record all elements that appear in the array, and a variable $ans$ to record the maximum positive integer that satisfies the problem requirements, initially $ans = -1$.

1

2

3

4

class Solution:
    def findMaxK(self, nums: List[int]) -> int:
        s = set(nums)
        return max((x for x in s if -x in s), default=-1)

Solution 2

#### Rust

1

2

3

4

class Solution:
    def findMaxK(self, nums: List[int]) -> int:
        s = set(nums)
        return max((x for x in s if -x in s), default=-1)

Continue Practicing

#2465 number of distinct averages #2491 divide players into teams of equal skill #2122 recover the original array