Cover image for LeetCode Daily Problem P2598 Maximum MEX After Operations

LeetCode Daily Problem P2598 Maximum MEX After Operations

(Updated: )
algorithm
, , ,
Timeline

timeline

2025-10-16

init

math

Problem:

P2598 Maximum after operations MEX

https://leetcode.cn/problems/smallest-missing-non-negative-integer-after-operations/description/?envType=daily-question&envId=2025-10-16

TLE

Use a min-heap to store the values of each number in nums after taking absolute value and modulo value, then count from the minimum. If the popped value from the min-heap equals the current number, add value to it and push back. Repeat until the heap is empty or a discontinuity appears. However, this O(n log n) method will time out.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <vector>
#include <algorithm>
#include <queue>

using std::priority_queue;
using std::vector;

class Solution {
    public:
	int cel_div(int a, int b)
	{
		return (a + b - 1) / b;
	}
	int findSmallestInteger(vector<int> &nums, int value)
	{
		// First convert all negative numbers to positive
		// Then convert all numbers to remainders modulo value

		int i;
		int n = nums.size();
		int top_value;
		int last_value;
		int count = 0;
		priority_queue<int, vector<int>, std::greater<int> > min_heap;

		for (i = 0; i < n; i++) {
			if (nums[i] < 0) {
				nums[i] += cel_div(-nums[i], value) * value;
			}
			nums[i] = nums[i] % value;
			min_heap.push(nums[i]);
		}

		last_value = -1;

		while (!min_heap.empty()) {
			top_value = min_heap.top();
			if (top_value == last_value) {
				min_heap.pop();
				min_heap.push(top_value + value);
				continue;
			}
			if (top_value != last_value + 1) {
				break;
			} else {
				last_value = top_value;
				min_heap.pop();
			}
		}

		return last_value + 1;
	}
};

int main()
{
	vector<int> vec = { 3, 0, 3, 2, 4, 2, 1, 1, 0, 4 };
	int value = 5;
	Solution s;
	s.findSmallestInteger(vec, value);
}

Mathematical optimization

All possible remainders modulo value form a set. Suppose there are group groups of all possible remainders modulo value, then the maximum of the final array is at leastvalue×group−1value \times group -1, remove the values of these groups from nums. Among the remaining, there must be a missing value from all possible remainders modulo value. Find the smallest missing value and addvalue×group−1value \times group -1That’s it. In programming, count the occurrences of each remainder, find the smallest count as group. The smallest cannot be 0,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <vector>
#include <algorithm>
#include <climits>
#include <unordered_map>

using std::vector;
using std::unordered_map;

class Solution {
    public:
	int cel_div(int a, int b)
	{
		return (a + b - 1) / b;
	}
	int findSmallestInteger(vector<int> &nums, int value)
	{
		// First, change all negative numbers to positive numbers.
		// Then, change all numbers to the remainder when divided by value.

		int i;
		int n = nums.size();
		int group = INT_MAX;

		int res;

		unordered_map<int, int> umap;

		if (value == 1) {
			return n - 1;
		}

		for (i = 0; i < n; i++) {
			if (nums[i] < 0) {
				nums[i] += cel_div(-nums[i], value) * value;
			}
			nums[i] = nums[i] % value;
			umap[nums[i]]++;
		}

		for (i = 0; i < value; i++) {
			if (umap.count(i) == 0) {
				return i;
			}
		}

		for (auto &[num, count] : umap) {
			if (count < group) {
				group = count;
				res = num;
			} else if (count == group) {
				res = std::min(res, num);
			}
		}

		res += group * value - 1;

		return res;
	}
};

int main()
{
	vector<int> vec = { 3, 2, 3, 1, 0, 1, 4, 2, 3, 1, 4, 1, 3 };
	int value = 5;
	Solution s;
	s.findSmallestInteger(vec, value);
}