Find the Next!

You are given an array A of length N. For any given integer X, you need to find an integer Z strictly greater than X such that Z is not present in the array A. You need to minimize the value of Z.

Example:

Input: n = 5, q = 2, arr = {2, 7, 5, 9, 15}, queries = {3, 9}

Output:

4
10

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

void findTheNext(int n, int q, vector<int> &arr,
                 vector<int> &queries)
{
    unordered_map<int, int> mp;
    sort(arr.begin(), arr.end());
    for (int i = 0; i < n;)
    {
        int j = i;
        for (j = i; j < n - 1; j++)
        {
            if (arr[j] < arr[j + 1] - 1)
                break;
        }
        for (int k = i; k <= j; k++)
            mp[arr[k]] = arr[j];
        i = j + 1;
    }

    for (int i = 0; i < q; i++)
    {
        int x = queries[i];

        if (mp[x] == 0)
        {
            if (mp[x + 1] == 0)
                cout << x + 1 << "\n";
            else
                cout << mp[x + 1] + 1 << "\n";
        }
        else
            cout << mp[x] + 1 << "\n";
    }
}
int main()
{

    int n = 5, q = 2;

    vector<int> arr = {2, 7, 5, 9, 15};
    vector<int> queries = {3, 9};

    findTheNext(n, q, arr, queries);

    return 0;
}