We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Largest Almost Missing Integer

Number: 3705

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an array of integers (nums) and an integer (k), identify the largest integer that appears in exactly one contiguous subarray of size k within nums. A subarray is defined as a contiguous sequence of k elements. If no integer satisfies this criterion, return -1.

Key Insights

  • Iterate over every possible subarray of length k in nums.
  • Use a set for each subarray to ensure each number is counted only once per subarray.
  • Use a hash table (dictionary) to count the number of subarrays each integer appears in.
  • The small constraints allow a solution with O(n*k) time complexity.
  • Finally, select the largest integer that has a count of exactly one, or return -1 if none exists.

Space and Time Complexity

Time Complexity: O(n*k), where n is the length of nums, since we examine each subarray of size k and handle each element in the subarray. Space Complexity: O(m), where m is the number of unique integers in nums (at most 51 given the constraints).

Solution

We slide a window of size k over the array. For each window (subarray), we use a set to capture unique numbers and update a counter for each number in a hash table. After processing every subarray, we iterate over the hash table to collect integers that appear exactly once, and then return the maximum among these values. If none exist, we return -1.

Code Solutions

# Python solution with comments

def largest_almost_missing(nums, k):
    # Dictionary to track the number of subarrays where each integer appears
    count = {}
    n = len(nums)
    
    # Iterate over each subarray of size k
    for i in range(n - k + 1):
        # Use a set to avoid duplicate counting within the same subarray
        unique_in_subarray = set(nums[i: i + k])
        for num in unique_in_subarray:
            count[num] = count.get(num, 0) + 1
    
    # Identify the largest integer that appears in exactly one subarray of size k
    candidate = -1
    for num, cnt in count.items():
        if cnt == 1:
            candidate = max(candidate, num)
    return candidate

# Example usage:
# print(largest_almost_missing([3, 9, 2, 1, 7], 3))
← Back to All Questions