algoadvance

Given an integer array nums that does not contain zeros, you need to find the largest positive integer k such that both k and -k exist in the array. If there is no such integer, return 0.

Clarifying Questions

1. Can the array contain duplicate values?
   • Yes, the array can contain duplicates.
2. Are the elements in the array positive, negative, or both?
   • The array can contain both positive and negative numbers.
3. What is the expected size range of the input array?
   • The array size is not specified, but typically we can assume standard constraints like up to 10^5 elements.

Strategy

1. Use a Set for Fast Lookups: We can use a set to keep track of the elements in the array since set lookups and insertions are average O(1) time complexity.
2. Iterate Over the Array: For each element in the array, we will check if both the element and its negative are present in the set.
3. Track the Largest Positive Integer: We will maintain a variable to keep track of the largest positive integer that meets the condition.
4. Return the Result: Finally, return the largest positive integer found, or 0 if no such integer exists.

Code

def findMaxK(nums):
    num_set = set(nums)
    largest_k = 0
    
    for num in nums:
        if -num in num_set and num > 0:
            largest_k = max(largest_k, num)
    
    return largest_k

# Example usage:
print(findMaxK([3, 2, -2, 5, -3]))  # Output should be 3
print(findMaxK([1, 2, 3, -4]))  # Output should be 0
print(findMaxK([-1, 10, 6, 7, -7, 1]))  # Output should be 7

Time Complexity

• Building the Set: O(n), where n is the number of elements in the array.
• Iterating Through the Array: O(n), we potentially check each element against the set.
• Overall: O(n) since the operations are linear with respect to the size of the input array.

This approach ensures that the solution is efficient and should work well within typical input size constraints.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?