Problem
Leet code problem 2441
Difficulty: Easy —
Solution
Initial approach
Utilize HashMap, iterate the whole array, for each item add it to the map. Each item should have one of the following value
- NEGATIVE ONLY
- POSITIVE ONLY
- FOUND BOTH NEGATIVE AND POSITIVE
This approach is cumbersome with lost of if else blocks
Second approach
Use HashSet instead
The concept is to put every item in the array to a set of unique items
After that find the max value among items that contains its counterpart
Implementation
Code from github
First approach (HashMap)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class L2441_LargestPositiveIntegerThatExistsWithItsNegative {
public static final int FOUND_BOTH_NEGATIVE_POSITIVE = 0;
public static final int FOUND_NEGATIVE = -1;
public static final int FOUND_POSITIVE = 1;
public int findMaxK(int[] nums) {
Map<Integer, Integer> resultMap = new HashMap();
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
if (!resultMap.containsKey(nums[i])) {
resultMap.put(nums[i], FOUND_POSITIVE);
} else if (resultMap.get(nums[i]) == FOUND_NEGATIVE) {
resultMap.put(nums[i], FOUND_BOTH_NEGATIVE_POSITIVE);
}
} else {
if (!resultMap.containsKey(-nums[i])) {
resultMap.put(-nums[i], FOUND_NEGATIVE);
} else if (resultMap.get(-nums[i]) == FOUND_POSITIVE) {
resultMap.put(-nums[i], FOUND_BOTH_NEGATIVE_POSITIVE);
}
}
}
int max = -1;
for (Map.Entry<Integer, Integer> entry : resultMap.entrySet()) {
if (entry.getValue() == FOUND_BOTH_NEGATIVE_POSITIVE && max < entry.getKey()) {
max = entry.getKey();
}
}
return max;
}
}
Second approach (HashSet)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class L2441_LargestPositiveIntegerThatExistsWithItsNegative {
public int findMaxK(int[] nums) {
Set<Integer> resultSet = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
resultSet.add(nums[i]);
}
int max = -1;
for (Integer item : resultSet) {
if (resultSet.contains(-item) && max < Math.abs(item)) {
max = Math.abs(item);
}
}
return max;
}
}