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.

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

 

Solutions

Solution: Hash Table

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
const largestInteger = function (nums, k) {
  const n = nums.length;

  if (k === n) return Math.max(...nums);

  const countMap = new Map();

  for (let index = 0; index < n; index++) {
    const num = nums[index];
    const count = countMap.get(num) ?? 0;

    countMap.set(num, count + 1);
  }

  if (k === 1) {
    let result = -1;

    for (const [num, count] of countMap) {
      if (count > 1) continue;

      result = Math.max(num, result);
    }

    return result;
  }

  const firstNum = nums[0];
  const lastNum = nums[n - 1];
  const firstCount = countMap.get(firstNum);
  const lastCount = countMap.get(lastNum);

  if (firstCount > 1 && lastCount > 1) return -1;

  if (firstCount > 1) return lastNum;

  if (lastCount > 1) return firstNum;

  return Math.max(firstNum, lastNum);
};