Largest Positive Integer That Exists With Its Negative

Largest Positive Integer That Exists With Its Negative - Problem

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.

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: 3 is the largest positive integer that has its negative -3 in the array. Both 2 and 3 have their negatives, but 3 is larger.

Example 2 — No Valid Pairs

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

› Output: 7

💡 Note: Only 7 has its negative -7 in the array. Numbers like 10, 6 don't have their negatives present.

Example 3 — No Pairs Exist

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

› Output: -1

💡 Note: None of the positive integers have their negative counterparts in the array.

Constraints

1 ≤ nums.length ≤ 1000
-1000 ≤ nums[i] ≤ 1000
nums[i] ≠ 0

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with positive and negative integers

Find Pairs

Identify positive numbers that have their negatives in the array

Return Maximum

Return the largest positive from valid pairs

Key Takeaway

🎯 Key Insight: Use a hash set for O(1) lookups to efficiently find positive-negative pairs

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to find positive-negative pairs efficiently. The hash set approach is optimal with O(n) time and O(n) space - store all numbers for O(1) lookup, then check each positive for its negative counterpart. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers - Sort First	O(n log n)	O(1)	Sort the array, then use two pointers to find complementary pairs
Brute Force - Check Every Pair	O(n²)	O(1)	For each positive number, search the entire array for its negative
Hash Set - Single Pass	O(n)	O(n)	Store all numbers in a set, then find the largest positive with its negative

Two Pointers - Sort First — Algorithm Steps

Step 1: Sort the array to enable two-pointer technique
Step 2: Use left and right pointers from both ends
Step 3: If sum is zero, we found a pair; adjust pointers based on sum

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Array

Sort to enable two-pointer technique

Use Pointers

Left and right pointers move based on sum

Find Pairs

When sum equals zero, we found a positive-negative pair

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int abs_val(int x) {
    return x < 0 ? -x : x;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), compare);
    int left = 0, right = numsSize - 1;
    int maxK = -1;
    
    while (left < right) {
        int currentSum = nums[left] + nums[right];
        if (currentSum == 0) {
            // Found a pair that sums to zero
            maxK = max(maxK, abs_val(nums[left]));
            left++;
            right--;
        } else if (currentSum < 0) {
            left++;  // Need larger sum
        } else {
            right--;  // Need smaller sum
        }
    }
    
    return maxK;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int nums[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), two-pointer scan takes O(n)

⚡ Linearithmic

Space Complexity

O(1)

Only using two pointer variables, sorting is in-place

✓ Linear Space

23.5K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers - Sort First — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler