3471. Find the Largest Almost Missing Integer

Problem Overview

x is almost missing when it sits in exactly one subarray of length k.

Intuition

x is almost missing when it sits in exactly one subarray of length k. The interesting windows always cover the interior, so most values appear in several windows. Only three cases matter: the whole array (k = n), each singleton (k = 1), or the two endpoints when 1 < k < n.

Algorithm

1If k == n, return the maximum of nums (one window contains every value).
2If k == 1, count frequencies in a size-51 array and return the largest value with count 1 (or -1).
3Otherwise scan once: an endpoint is a candidate only if that value never appears elsewhere.
4Return the max of the unique endpoints, or -1 if neither is unique.

Example Walkthrough

Input: nums = [3, 9, 2, 1, 7], k = 3

1.k is neither 1 nor n, so only 3 and 7 can be unique-window values.
2.3 and 7 each appear once in the array, so both are candidates.
3.The larger is 7.

Output: 7

Common Pitfalls

•Values in the middle of the array always sit in more than one k-window when 1 < k < n.
•k == 1 is not the same as uniqueness of endpoints - every singleton window counts, so take the largest globally unique number.
•If the two endpoints are the same unique value, it still appears twice, so it is not almost missing.
•Return -1 when no candidate exists, not 0.

3471.cs

// Approach: An integer is almost missing if it appears in exactly one k-window.
// k == n: the whole array is that window, so answer is max(nums).
// k == 1: each element is its own window, so answer is the largest unique value.
// Else only nums[0] / nums[n-1] can sit in a unique window; take the larger
// one that appears once in the whole array (else -1).
// Complexity: O(n) time and O(1) space.
public class Solution
{
    public int LargestInteger(int[] nums, int k)
    {
        int n = nums.Length;

        if (k == n)
        {
            int max = nums[0];
            for (int i = 1; i < n; i++)
            {
                if (nums[i] > max)
                    max = nums[i];
            }
            return max;
        }

        if (k == 1)
        {
            int[] count = new int[51];
            foreach (int x in nums)
                count[x]++;

            for (int v = 50; v >= 0; v--)
            {
                if (count[v] == 1)
                    return v;
            }
            return -1;
        }

        int first = nums[0], last = nums[n - 1];
        bool firstUnique = true, lastUnique = true;
        for (int i = 0; i < n; i++)
        {
            if (i != 0 && nums[i] == first)
                firstUnique = false;
            if (i != n - 1 && nums[i] == last)
                lastUnique = false;
        }

        int ans = -1;
        if (firstUnique)
            ans = first;
        if (lastUnique && last > ans)
            ans = last;
        return ans;
    }
}

Was this solution helpful?