3705. Find The Largest Almost Missing Integer¶

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.

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.

Input: nums = [0,0], k = 1

Output: -1

Explanation:

There is no integer that appears in only one subarray of size 1.

class Solution {
    public int largestInteger(int[] nums, int k) {
        int n = nums.length;
        int maxi = Integer.MIN_VALUE;
        for (int ele : nums) {
            if (check(ele, nums, k)) {
                maxi = Math.max(maxi, ele);
            }
        }
        if (maxi == Integer.MIN_VALUE) return -1;
        return maxi;
    }
    private boolean check(int target, int arr[], int k) {
        int n = arr.length;
        int count = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < k; i++) {
            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
        }
        if (map.getOrDefault(target, 0) > 0) count++;
        int start = 0;
        for (int i = k; i < n; i++) {
            map.put(arr[start], map.getOrDefault(arr[start], 0) -1);
            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
            if (map.getOrDefault(target, 0) > 0) count++;
            start++;
        }
        return count == 1;
    }
}