algoadvance

Leetcode 2441. Largest Positive Integer That Exists With Its Negative

Problem Statement

You are 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.

Clarifying Questions

  1. Can the array contain duplicate elements?
    • Yes, the array can contain duplicate elements.
  2. What is the range of the number of elements in the array?
    • The size of the array ranges from 1 to 1000.
  3. What is the range of the elements in the array?
    • The elements in the array range from -1000 to 1000.

Strategy

  1. Use a Set for Lookup:
    • We can use a HashSet to keep track of the elements in the array because it allows for average O(1) time complexity for add and contains operations.
  2. Iterate and Check:
    • Iterate through the array and for each positive number, check if its negative counterpart exists in the set.
    • Keep track of the largest such positive number found.

Code

Let’s implement this strategy in Java:

import java.util.HashSet;

public class Solution {
    public int findMaxK(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        int maxK = -1;
        
        // Add all elements to the set
        for (int num : nums) {
            set.add(num);
        }
        
        // Check for the largest positive number k such that -k exists
        for (int num : nums) {
            if (num > 0 && set.contains(-num)) {
                maxK = Math.max(maxK, num);
            }
        }
        
        return maxK;
    }

    // Example test for verification
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {3, 2, -2, 5, -3};
        System.out.println(solution.findMaxK(nums)); // Output should be 3
    }
}

Time Complexity

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