Find the Largest Almost Missing Integer - Practice Coding Problems

Find the Largest Almost Missing Integer - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,3,2,4], k = 3

› Output: 4

💡 Note: Subarrays: [1,2,3], [2,3,2], [3,2,4]. Number 4 appears in exactly one subarray [3,2,4], and it's the largest such number.

Example 2 — No Almost Missing

$ Input: nums = [1,2,3,1,2,3], k = 2

› Output: -1

💡 Note: All subarrays: [1,2], [2,3], [3,1], [1,2], [2,3]. Every unique number appears in multiple subarrays, so no almost missing integer exists.

Example 3 — Single Element Window

$ Input: nums = [5,3,7,3,5], k = 1

› Output: 7

💡 Note: Each element forms its own subarray. Number 7 appears in exactly one subarray and is the largest among such numbers.

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ k ≤ nums.length
-1000 ≤ nums[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums and window size k

Process

Count subarray appearances for each number

Output

Largest number appearing exactly once

Key Takeaway

🎯 Key Insight: Count subarray appearances for each number and find the largest with exactly one occurrence

Asked in

G Google 15 M Microsoft 12

The key insight is to count how many subarrays of size k contain each number, then find the largest number that appears in exactly one subarray. Best approach uses frequency counting with hash map. Time: O(n×k), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n×k)	O(n)	Generate all subarrays and count occurrences of each element
Sliding Window Optimization	O(n×k)	O(n)	Use sliding window to efficiently generate subarrays and track frequencies
Optimized Frequency Tracking	O(n×k)	O(n)	Direct frequency counting with single pass through subarrays

Brute Force — Algorithm Steps

Generate all subarrays of size k
For each subarray, track which numbers appear
Count total occurrences of each number
Return largest number with count = 1

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subarrays

Create all possible subarrays of size k

Count Frequencies

Track how many subarrays contain each number

Find Maximum

Return largest number appearing exactly once

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 1000

int solution(int* nums, int numsSize, int k) {
    if (numsSize < k) return -1;
    
    int count[2001] = {0}; // Assuming range -1000 to 1000
    int offset = 1000; // Handle negative numbers
    
    // Generate all subarrays of size k
    for (int i = 0; i <= numsSize - k; i++) {
        int seen[2001] = {0};
        for (int j = i; j < i + k; j++) {
            seen[nums[j] + offset] = 1;
        }
        for (int j = 0; j < 2001; j++) {
            if (seen[j]) {
                count[j]++;
            }
        }
    }
    
    // Find largest number that appears exactly once
    int result = -1;
    for (int i = 2000; i >= 0; i--) {
        if (count[i] == 1) {
            result = i - offset;
            break;
        }
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[MAX_SIZE];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]"); // Skip opening bracket
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×k)

Generate n-k+1 subarrays, process k elements in each

✓ Linear Growth

Space Complexity

O(n)

Hash map stores frequency count for each unique number

⚡ Linearithmic Space

8.4K Views

Medium Frequency

~15 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler