3471. Find the Largest Almost Missing Integer

EasyArrayHash Table

Problem 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.

Intuition

To solve the problem, we need to identify the integers that appear in exactly one subarray of size k. The approach varies based on the value of k:

Case 1: If k = 1, each element in nums forms a subarray of size 1. We then need to find the maximum integer that appears exactly once in the entire array. This is done by counting the occurrences of each integer and selecting the largest one that appears only once.
Case 2: If k equals the length of nums, the whole array itself is a subarray. Hence, the largest almost missing integer would be the largest integer in nums, as every integer appears in exactly one 'subarray' (i.e., the array itself).
Case 3: If 1 < k < n (where n is the length of nums), only the first and last elements (nums[0] and nums[n-1]) can potentially be almost missing, as any integer appearing elsewhere would appear in more than one contiguous subarray. We check if nums[0] or nums[n-1] appear anywhere else in the array and select the largest among those that appear only once.

If no integer fits the criteria of being almost missing, we return -1.

Solution Approach

The solution is implemented through several key steps based on the different cases for k:

Case Analysis:
- Case 1: When k = 1, we calculate the frequency of each element in nums using a counter. We then find the maximum element that appears exactly once in nums. This requires iterating through the counter's items and using the max function to select the appropriate element, with a default of -1 if no such element exists.
- Case 2: When k equals the length of nums, we simply return the maximum value in nums because every element is part of the only subarray that is the entire array itself.
- Case 3: When 1 < k < n, we are interested in the edge elements nums[0] and nums[n-1]. For these, we define a function f(k) that checks if nums[k] appears elsewhere in the array. If it does, it is not almost missing, and we return -1. Otherwise, we return the value of nums[k]. The result is the maximum of f(0) and f(len(nums) - 1), ensuring that if neither is almost missing, we return -1.

Using Counter for frequency counting allows us to efficiently handle case 1, while leveraging list indexing and a helper function allows us to handle the edge elements in case 3. This streamlined approach effectively checks all conditions with minimal computations.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate the solution approach.

Consider the integer array nums = [5, 1, 5, 3, 5] and k = 1.

Case 1: Since k = 1, each element is its own subarray. We need to determine the largest integer that appears exactly once in the entire array.
1. Calculate the frequency of each element in nums. We get Counter({5: 3, 1: 1, 3: 1}).
2. Identify elements that occur only once: 1 and 3.
3. Determine the largest element among these: 3.
Hence, the output is 3.

Now, let's consider nums = [7, 8, 9] and k = 3.

Case 2: Here, k is the length of nums, so the entire array itself is a subarray. The largest integer appearing in exactly one full-array subarray is simply the maximum element in nums.

The maximum value in nums is 9.

Thus, the output is 9.

For nums = [4, 2, 4, 2, 6] and k = 3, refer to Case 3.

Case 3: Here, 1 < k < n, with n = 5. We need to check the edge elements nums[0] and nums[4].
1. nums[0] = 4 is checked against its subsequent occurrences. Since 4 appears again in the array, it is not almost missing.
2. nums[4] = 6 is checked for other occurrences. As it doesn't appear elsewhere, it is almost missing.
Therefore, the largest almost missing element is 6.

Thus, the output is 6.

Solution Implementation

1from typing import List
2from collections import Counter
3
4class Solution:
5    def largestInteger(self, nums: List[int], k: int) -> int:
6        # Define a helper function that checks for a specific condition on the list
7        def check_unique_index(index: int) -> int:
8            # Iterate through the list
9            for i, value in enumerate(nums):
10                # If the index isn't the same and the values match, return -1
11                if i != index and value == nums[index]:
12                    return -1
13            # If unique, return the value at the given index
14            return nums[index]
15
16        # If we need to find the largest integer with exactly one occurrence
17        if k == 1:
18            count = Counter(nums)
19            # Find the largest integer that appears exactly once
20            return max((num for num, occurences in count.items() if occurences == 1), default=-1)
21      
22        # If the problem is looking for the largest integer in the entire list
23        if k == len(nums):
24            return max(nums)
25      
26        # Otherwise, check the largest value between the condition tested on first and last index
27        return max(check_unique_index(0), check_unique_index(len(nums) - 1))
28

1import java.util.Arrays;
2import java.util.HashMap;
3import java.util.Map;
4
5class Solution {
6    private int[] nums; // Declare a private instance variable to store the input array
7
8    /**
9     * Determines the largest integer in the array under specific conditions
10     */
11    public int largestInteger(int[] nums, int k) {
12        this.nums = nums; // Initialize the instance variable with the input array
13
14        if (k == 1) {
15            // If k is 1, find the maximum unique number
16            Map<Integer, Integer> cnt = new HashMap<>();
17            for (int x : nums) {
18                // Count the occurrences of each number in the array
19                cnt.merge(x, 1, Integer::sum);
20            }
21            int ans = -1;
22            for (var e : cnt.entrySet()) {
23                // Check for numbers with exactly one occurrence and find the maximum
24                if (e.getValue() == 1) {
25                    ans = Math.max(ans, e.getKey());
26                }
27            }
28            return ans;
29        }
30
31        if (k == nums.length) {
32            // If k is equal to the length of the array, return the maximum number in the array
33            return Arrays.stream(nums).max().getAsInt();
34        }
35
36        // When k is neither 1 nor the length of the array, compute max using helper function 'f'
37        return Math.max(f(0), f(nums.length - 1));
38    }
39
40    /**
41     * Helper function to determine the value of the number at position k
42     * Returns -1 if the number is not unique, otherwise returns the number.
43     */
44    private int f(int k) {
45        for (int i = 0; i < nums.length; ++i) {
46            if (i != k && nums[i] == nums[k]) {
47                // If another number in the array matches the number at position k, return -1
48                return -1;
49            }
50        }
51        // If the number at position k is unique, return the number
52        return nums[k];
53    }
54}
55

1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4
5class Solution {
6public:
7    int largestInteger(std::vector<int>& nums, int k) {
8        // Check if k is 1
9        if (k == 1) {
10            std::unordered_map<int, int> count;
11            // Count the occurrences of each number
12            for (int num : nums) {
13                ++count[num];
14            }
15            int max_value = -1;
16            // Find the maximum among numbers appearing exactly once
17            for (auto& [num, occurrences] : count) {
18                if (occurrences == 1) {
19                    max_value = std::max(max_value, num);
20                }
21            }
22            return max_value;
23        }
24      
25        int n = nums.size();
26      
27        // If k is equal to the size of nums, return the maximum element
28        if (k == n) {
29            return *std::max_element(nums.begin(), nums.end());
30        }
31      
32        // Function to find the value at index k if it is unique
33        auto checkUnique = [&](int k) -> int {
34            for (int i = 0; i < n; ++i) {
35                if (i != k && nums[i] == nums[k]) {
36                    return -1; // Return -1 if not unique
37                }
38            }
39            return nums[k]; // Return the value if it's unique
40        };
41      
42        // Check both ends of the array for unique values and return the maximum
43        return std::max(checkUnique(0), checkUnique(n - 1));
44    }
45};
46

1// Function to find the largest integer according to the given logic
2function largestInteger(nums: number[], k: number): number {
3    // Special case when k is 1
4    if (k === 1) {
5        // Create a map to count occurrences of each number
6        const cnt = new Map<number, number>();
7        for (const num of nums) {
8            cnt.set(num, (cnt.get(num) || 0) + 1);
9        }
10      
11        // Variable to track the largest unique number, initialize with -1
12        let maxUnique = -1;
13      
14        // Iterate through the map to find the largest unique number
15        for (const [num, count] of cnt.entries()) {
16            if (count === 1 && num > maxUnique) {
17                maxUnique = num;
18            }
19        }
20      
21        return maxUnique;
22    }
23
24    const n = nums.length;
25
26    // Special case when k is equal to the size of the array
27    if (k === n) {
28        // Return the maximum number in the array
29        return Math.max(...nums);
30    }
31
32    // Helper function to check for duplicates of nums[k]
33    const findUnique = (index: number): number => {
34        for (let i = 0; i < n; i++) {
35            if (i !== index && nums[i] === nums[index]) {
36                return -1; // Return -1 if a duplicate is found
37            }
38        }
39        return nums[index]; // Return nums[index] if it is unique
40    };
41
42    // Return the maximum value between the first and last elements checked for uniqueness
43    return Math.max(findUnique(0), findUnique(n - 1));
44}
45

Time and Space Complexity

The time complexity of the code is O(n) because each relevant operation, including creating a Counter and iterating over nums, takes linear time proportional to the number of elements in the input list nums. In the worst case, it requires traversing the entire list a few times due to the nested function executions and Counter creation.

The space complexity is also O(n) since it involves storing data in a Counter object, which requires additional storage proportional to the number of distinct elements in nums.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don't know