3471. Find the Largest Almost Missing Integer LeetCode Solution

In this guide, you will get 3471. Find the Largest Almost Missing Integer LeetCode Solution with the best time and space complexity. The solution to Find the Largest Almost Missing Integer problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Find the Largest Almost Missing Integer solution in C++
Find the Largest Almost Missing Integer solution in Java
Find the Largest Almost Missing Integer solution in Python
Additional Resources

3471. Find the Largest Almost Missing Integer LeetCode Solution image

Problem Statement of Find the Largest Almost Missing Integer

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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(50) = O(1)

3471. Find the Largest Almost Missing Integer LeetCode Solution in C++

class Solution {
 public:
  int largestInteger(vector<int>& nums, int k) {
    if (k == nums.size())
      return ranges::max(nums);
    const vector<int> count = getCount(nums);
    if (k == 1)
      return maxUnique(nums, count);
    return max(count[nums.front()] == 1 ? nums.front() : -1,
               count[nums.back()] == 1 ? nums.back() : -1);
  }

 private:
  // Returns the maximum unique integer in nums if any. Otherwise, returns -1.
  int maxUnique(const vector<int>& nums, const vector<int>& count) {
    int maxUnique = -1;
    for (const int num : nums)
      if (count[num] == 1)
        maxUnique = max(maxUnique, num);
    return maxUnique;
  }

  vector<int> getCount(const vector<int>& nums) {
    constexpr int kMax = 50;
    vector<int> count(kMax + 1);
    for (const int num : nums)
      ++count[num];
    return count;
  }
};
/* code provided by PROGIEZ */

3471. Find the Largest Almost Missing Integer LeetCode Solution in Java

class Solution {
  public int largestInteger(int[] nums, int k) {
    if (k == nums.length)
      return Arrays.stream(nums).max().getAsInt();
    int[] count = getCount(nums);
    if (k == 1)
      return maxUnique(nums, count);
    return Math.max(count[nums[0]] == 1 ? nums[0] : -1,
                    count[nums[nums.length - 1]] == 1 ? nums[nums.length - 1] : -1);
  }

  // Returns the maximum unique integer in nums if any. Otherwise, returns -1.
  private int maxUnique(int[] nums, int[] count) {
    return Arrays.stream(nums).filter(num -> count[num] == 1).max().orElse(-1);
  }

  private int[] getCount(int[] nums) {
    final int MAX = 50;
    int[] count = new int[MAX + 1];
    for (final int num : nums)
      ++count[num];
    return count;
  }
}
// code provided by PROGIEZ

3471. Find the Largest Almost Missing Integer LeetCode Solution in Python

class Solution:
  def largestInteger(self, nums: list[int], k: int) -> int:
    if k == len(nums):
      return max(nums)
    count = collections.Counter(nums)
    if k == 1:
      return max([num for num in nums if count[num] == 1], default=-1)
    return max(
        nums[0] if count[nums[0]] == 1 else -1,
        nums[-1] if count[nums[-1]] == 1 else -1
    )
 # code by PROGIEZ