Watch 10 video solutions for Largest Positive Integer That Exists With Its Negative, a easy level problem involving Array, Hash Table, Two Pointers. This walkthrough by codestorywithMIK has 4,031 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 1:
Input: nums = [-1,2,-3,3] Output: 3 Explanation: 3 is the only valid k we can find in the array.
Example 2:
Input: nums = [-1,10,6,7,-7,1] Output: 7 Explanation: 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 Explanation: There is no a single valid k, we return -1.
Constraints:
1 <= nums.length <= 1000-1000 <= nums[i] <= 1000nums[i] != 0Problem Overview: You are given an integer array nums. The task is to find the largest positive integer k such that both k and -k appear in the array. If no such integer exists, return -1. The goal is to efficiently detect matching positive–negative pairs and track the maximum valid value.
Approach 1: Using HashSet for Fast Lookup (O(n) time, O(n) space)
This approach relies on a hash set for constant‑time lookups. First iterate through the array and insert each number into a HashSet. Then iterate again and check whether the opposite value (-num) exists in the set. Whenever both numbers exist, update the answer with the maximum positive value encountered. Because each lookup is O(1) on average, the full scan takes O(n) time while storing elements requires O(n) space. This is the most direct solution using a Hash Table and works well for unsorted input arrays.
Approach 2: Sorting to Simplify Pair Search (O(n log n) time, O(1) extra space)
Sorting the array groups negative and positive numbers in order, which makes it easier to find matching pairs. After sorting, use two pointers: one starting from the left (most negative) and one from the right (largest positive). Compare the absolute values of the numbers. If they match, you found a valid pair and can return that positive number immediately. If the absolute value on the left is larger, move the left pointer forward; otherwise move the right pointer backward. Sorting costs O(n log n), and the two‑pointer scan runs in O(n) time with O(1) additional space. This method combines Sorting with the Two Pointers technique.
Recommended for interviews: The hash set approach is typically expected because it achieves optimal O(n) time and is straightforward to implement. Interviewers want to see that you recognize the symmetric relationship between k and -k and use constant‑time lookups to detect pairs efficiently. The sorting approach is still valuable because it demonstrates comfort with pointer techniques and problem transformation, but it is slightly less optimal due to the sorting step.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashSet Fast Lookup | O(n) | O(n) | Best general solution when the array is unsorted and fast membership checks are needed |
| Sorting + Two Pointers | O(n log n) | O(1) | Useful when sorting is acceptable or when practicing two-pointer techniques |