Welcome to Subscribe On Youtube
3371. Identify the Largest Outlier in an Array
Description
You are given an integer array nums. This array contains n elements, where exactly n - 2 elements are special numbers. One of the remaining two elements is the sum of these special numbers, and the other is an outlier.
An outlier is defined as a number that is neither one of the original special numbers nor the element representing the sum of those numbers.
Note that special numbers, the sum element, and the outlier must have distinct indices, but may share the same value.
Return the largest potential outlier in nums.
Example 1:
Input: nums = [2,3,5,10]
Output: 10
Explanation:
The special numbers could be 2 and 3, thus making their sum 5 and the outlier 10.
Example 2:
Input: nums = [-2,-1,-3,-6,4]
Output: 4
Explanation:
The special numbers could be -2, -1, and -3, thus making their sum -6 and the outlier 4.
Example 3:
Input: nums = [1,1,1,1,1,5,5]
Output: 5
Explanation:
The special numbers could be 1, 1, 1, 1, and 1, thus making their sum 5 and the other 5 as the outlier.
Constraints:
3 <= nums.length <= 105-1000 <= nums[i] <= 1000- The input is generated such that at least one potential outlier exists in
nums.
Solutions
Solution 1: Hash Table + Enumeration
We use a hash table $\textit{cnt}$ to record the frequency of each element in the array $\textit{nums}$.
Next, we enumerate each element $x$ in the array $\textit{nums}$ as a possible outlier. For each $x$, we calculate the sum $t$ of all elements in the array $\textit{nums}$ except $x$. If $t$ is not even, or half of $t$ is not in $\textit{cnt}$, then $x$ does not meet the condition, and we skip this $x$. Otherwise, if $x$ is not equal to half of $t$, or $x$ appears more than once in $\textit{cnt}$, then $x$ is a possible outlier, and we update the answer.
After enumerating all elements, we return the answer.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $\textit{nums}$.
-
class Solution { public int getLargestOutlier(int[] nums) { int s = 0; Map<Integer, Integer> cnt = new HashMap<>(); for (int x : nums) { s += x; cnt.merge(x, 1, Integer::sum); } int ans = Integer.MIN_VALUE; for (var e : cnt.entrySet()) { int x = e.getKey(), v = e.getValue(); int t = s - x; if (t % 2 != 0 || !cnt.containsKey(t / 2)) { continue; } if (x != t / 2 || v > 1) { ans = Math.max(ans, x); } } return ans; } } -
class Solution { public: int getLargestOutlier(vector<int>& nums) { int s = 0; unordered_map<int, int> cnt; for (int x : nums) { s += x; cnt[x]++; } int ans = INT_MIN; for (auto [x, v] : cnt) { int t = s - x; if (t % 2 || !cnt.contains(t / 2)) { continue; } if (x != t / 2 || v > 1) { ans = max(ans, x); } } return ans; } }; -
class Solution: def getLargestOutlier(self, nums: List[int]) -> int: s = sum(nums) cnt = Counter(nums) ans = -inf for x, v in cnt.items(): t = s - x if t % 2 or cnt[t // 2] == 0: continue if x != t // 2 or v > 1: ans = max(ans, x) return ans -
func getLargestOutlier(nums []int) int { s := 0 cnt := map[int]int{} for _, x := range nums { s += x cnt[x]++ } ans := math.MinInt32 for x, v := range cnt { t := s - x if t%2 != 0 || cnt[t/2] == 0 { continue } if x != t/2 || v > 1 { ans = max(ans, x) } } return ans } -
function getLargestOutlier(nums: number[]): number { let s = 0; const cnt: Record<number, number> = {}; for (const x of nums) { s += x; cnt[x] = (cnt[x] || 0) + 1; } let ans = -Infinity; for (const [x, v] of Object.entries(cnt)) { const t = s - +x; if (t % 2 || !cnt.hasOwnProperty((t / 2) | 0)) { continue; } if (+x != ((t / 2) | 0) || v > 1) { ans = Math.max(ans, +x); } } return ans; }