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 largestalmost missing integer from nums. If no such integer exists, return -1.
A subarray is a contiguous sequence of elements within an array.
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 <= 50
0 <= nums[i] <= 50
1 <= k <= nums.length
My Solution
There are two special cases in this problem. If k is equal to the length of the array, then the largest almost missing integer is simply the maximum element since there is only one subarray. Otherwise, we just keep counts of all elements. The other special case is if k is equal to 1, in which case we return the maximum element in the array that only appears once. In all other cases the only elements that are present in only one subarray are the first and last element, so we can just return the maximum of those two if they appear only once in the array. If none of these cases apply, we simply return -1.
Time complexity is O(n), where n is the length of the array because we need to keep counts of the elements. Space complexity is O(n) to keep the counts.
class Solution {
public int largestInteger(int[] nums, int k) {
Map<Integer,Integer> counts = new HashMap<>();
int n = nums.length;
int max = -1;
for (int i = 0; i < n; i++) {
counts.put(nums[i], counts.getOrDefault(nums[i],0)+1);
}
if (k == n) {
for (int i = 0; i < n; i++) {
max = Math.max(max, nums[i]);
}
return max;
}
if (k == 1) {
for (int i = 0; i < n; i++) {
if (counts.get(nums[i]) == 1) {
max = Math.max(max, nums[i]);
}
}
return max;
}
if (counts.get(nums[0]) == 1) {
max = Math.max(max, nums[0]);
}
if (counts.get(nums[n-1]) == 1) {
max = Math.max(max, nums[n-1]);
}
return max;
}
}