3471. Find the Largest Almost Missing Integer
Description
You are given an integer array nums and an integer k.
An integer x is almost missing from nums if x appears in exactly one subarray of size k within nums.
Return the largest almost missing integer from nums. If no such integer exists, return -1.
Example 1:
Input: nums = [3,9,2,1,7], k = 3
Output: 7
Explanation:
- 1 appears in 2 subarrays of size 3:
[9, 2, 1]and[2, 1, 7]. - 2 appears in 3 subarrays of size 3:
[3, 9, 2],[9, 2, 1],[2, 1, 7]. - 3 appears in 1 subarray of size 3:
[3, 9, 2]. - 7 appears in 1 subarray of size 3:
[2, 1, 7]. - 9 appears in 2 subarrays of size 3:
[3, 9, 2], and[9, 2, 1].
We return 7 since it is the largest integer that appears in exactly one subarray of size k.
Example 2:
Input: nums = [3,9,7,2,1,7], k = 4
Output: 3
Explanation:
- 1 appears in 2 subarrays of size 4:
[9, 7, 2, 1],[7, 2, 1, 7]. - 2 appears in 3 subarrays of size 4:
[3, 9, 7, 2],[9, 7, 2, 1],[7, 2, 1, 7]. - 3 appears in 1 subarray of size 4:
[3, 9, 7, 2]. - 7 appears in 3 subarrays of size 4:
[3, 9, 7, 2],[9, 7, 2, 1],[7, 2, 1, 7]. - 9 appears in 2 subarrays of size 4:
[3, 9, 7, 2],[9, 7, 2, 1].
We return 3 since it is the largest and only integer that appears in exactly one subarray of size k.
Example 3:
Input: nums = [0,0], k = 1
Output: -1
Explanation:
There is no integer that appears in only one subarray of size 1.
Constraints:
1 <= nums.length <= 500 <= nums[i] <= 501 <= k <= nums.length
Solutions
Solution 1: Case Analysis
If $k = 1$, then each element in the array forms a subarray of size $1$. In this case, we only need to find the maximum value among the elements that appear exactly once in the array.
If $k = n$, then the entire array forms a subarray of size $n$. In this case, we only need to return the maximum value in the array.
If $1 < k < n$, only $\textit{nums}[0]$ and $\textit{nums}[n-1]$ can be the almost missing integers. If they appear elsewhere in the array, they are not almost missing integers. Therefore, we only need to check if $\textit{nums}[0]$ and $\textit{nums}[n-1]$ appear elsewhere in the array and return the maximum value among them.
If no almost missing integer exists, return $-1$.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $\textit{nums}$.
Python3
class Solution:
def largestInteger(self, nums: List[int], k: int) -> int:
def f(k: int) -> int:
for i, x in enumerate(nums):
if i != k and x == nums[k]:
return -1
return nums[k]
if k == 1:
cnt = Counter(nums)
return max((x for x, v in cnt.items() if v == 1), default=-1)
if k == len(nums):
return max(nums)
return max(f(0), f(len(nums) - 1))
Java
class Solution {
private int[] nums;
public int largestInteger(int[] nums, int k) {
this.nums = nums;
if (k == 1) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums) {
cnt.merge(x, 1, Integer::sum);
}
int ans = -1;
for (var e : cnt.entrySet()) {
if (e.getValue() == 1) {
ans = Math.max(ans, e.getKey());
}
}
return ans;
}
if (k == nums.length) {
return Arrays.stream(nums).max().getAsInt();
}
return Math.max(f(0), f(nums.length - 1));
}
private int f(int k) {
for (int i = 0; i < nums.length; ++i) {
if (i != k && nums[i] == nums[k]) {
return -1;
}
}
return nums[k];
}
}
C++
class Solution {
public:
int largestInteger(vector<int>& nums, int k) {
if (k == 1) {
unordered_map<int, int> cnt;
for (int x : nums) {
++cnt[x];
}
int ans = -1;
for (auto& [x, v] : cnt) {
if (v == 1) {
ans = max(ans, x);
}
}
return ans;
}
int n = nums.size();
if (k == n) {
return ranges::max(nums);
}
auto f = [&](int k) -> int {
for (int i = 0; i < n; ++i) {
if (i != k && nums[i] == nums[k]) {
return -1;
}
}
return nums[k];
};
return max(f(0), f(n - 1));
}
};
Go
func largestInteger(nums []int, k int) int {
if k == 1 {
cnt := make(map[int]int)
for _, x := range nums {
cnt[x]++
}
ans := -1
for x, v := range cnt {
if v == 1 {
ans = max(ans, x)
}
}
return ans
}
n := len(nums)
if k == n {
return slices.Max(nums)
}
f := func(k int) int {
for i, x := range nums {
if i != k && x == nums[k] {
return -1
}
}
return nums[k]
}
return max(f(0), f(n-1))
}
TypeScript
function largestInteger(nums: number[], k: number): number {
if (k === 1) {
const cnt = new Map<number, number>();
for (const x of nums) {
cnt.set(x, (cnt.get(x) || 0) + 1);
}
let ans = -1;
for (const [x, v] of cnt.entries()) {
if (v === 1 && x > ans) {
ans = x;
}
}
return ans;
}
const n = nums.length;
if (k === n) {
return Math.max(...nums);
}
const f = (k: number): number => {
for (let i = 0; i < n; i++) {
if (i !== k && nums[i] === nums[k]) {
return -1;
}
}
return nums[k];
};
return Math.max(f(0), f(n - 1));
}