Leetcode 2441: Largest Positive Integer That Exists With Its Negative
You are given an integer array
nums where each element is non-zero. Your task is to find the largest positive integer k such that its negative counterpart -k also exists in the array. Return the largest such k. If no such integer exists, return -1.Problem
Approach
Steps
Complexity
Input: The input is a non-empty array `nums` of integers, where each integer is non-zero.
Example: nums = [4, -2, -4, 5, 1]
Constraints:
• 1 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• nums[i] != 0
Output: Return the largest integer `k` such that `-k` exists in the array. If no such `k` exists, return -1.
Example: Output: 4
Constraints:
• The returned result must be an integer.
Goal: The goal is to find the largest integer `k` such that `-k` exists in the array.
Steps:
• 1. Iterate through the array and store the presence of each number in a hash map.
• 2. For each positive integer `k` in the array, check if its negative counterpart `-k` is also present.
• 3. Track the largest valid `k` found during the iteration and return it.
Goal: The solution should handle arrays of size up to 1000 and should be able to efficiently find the largest `k`.
Steps:
• Arrays will always contain non-zero integers.
Assumptions:
• The input array will always contain at least one element.
• There will be no zeroes in the input array.
• Input: nums = [4, -2, -4, 5, 1]
• Explanation: Here, the number `4` has its negative counterpart `-4` in the array. The number `2` has `-2`, but the largest such integer is `4`. Hence, the output is 4.
• Input: nums = [-6, -3, 5, 2]
• Explanation: There is no positive integer `k` such that `-k` is present in the array. Therefore, the output is -1.
Approach: To solve this problem, we need to efficiently check for each number if its negative counterpart exists in the array. Using a hash map allows us to check for presence in constant time.
Observations:
• We can use a hash set to track the numbers that we encounter in the array.
• After processing all numbers, we can iterate through the positive numbers and check if their negatives exist.
• A direct approach using a hash set will be both time-efficient and simple to implement.
Steps:
• 1. Create a hash set to store the elements of the array.
• 2. Iterate through the array and for each element, check if its negative counterpart exists in the hash set.
• 3. Track the largest valid `k` during the iteration and return it at the end.
Empty Inputs:
• There will always be at least one non-zero element in the input array, so empty arrays are not a concern.
Large Inputs:
• The solution should be able to handle arrays with up to 1000 elements efficiently.
Special Values:
• When the array contains both positive and negative numbers, the solution should correctly identify pairs such as `3` and `-3`.
Constraints:
• The solution must check for both positive and negative values in the array.
int findMaxK(vector<int>& nums) {
int arr[2001] = {}, res = -1;
for (int n : nums) {
if (arr[-n + 1000])
res = max(res, abs(n));
++arr[n + 1000];
}
return res;
}
1 : Function Definition
int findMaxK(vector<int>& nums) {
Defining the function `findMaxK`, which takes a vector `nums` and returns an integer representing the largest `k` such that both `k` and `-k` are present in the array.
2 : Variable Initialization
int arr[2001] = {}, res = -1;
Initializing an auxiliary array `arr` of size 2001 to track the occurrence of integers from -1000 to 1000 (mapped to indices 0 to 2000). `res` is initialized to -1, which will store the result.
3 : Loop
for (int n : nums) {
Iterating through each integer `n` in the `nums` array.
4 : Condition Check
if (arr[-n + 1000])
Checking if the corresponding negative integer `-n` has already appeared in the array by using the auxiliary array `arr`. The `-n + 1000` adjusts for negative indices.
5 : Mathematical Operation
res = max(res, abs(n));
If both `n` and `-n` are found, update the result `res` to be the maximum of the current `res` and the absolute value of `n`.
6 : Array Update
++arr[n + 1000];
Incrementing the value at the index corresponding to `n` in the auxiliary array `arr` to mark that `n` has been encountered.
7 : Return Statement
return res;
Returning the result `res`, which holds the largest integer `k` such that both `k` and `-k` are present in the array, or -1 if no such pair exists.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the length of the array, since we perform constant-time operations for each element.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the hash set used to store the elements of the array.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus