MediumNo. 2598
Smallest Missing Non-negative Integer After Operations — LeetCode 2598 Python Solution
- Pattern
- Greedy
- Topics
- Greedy, Array, Hash Table, Math
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given a 0-indexed integer array nums and an integer value. In one operation, you can add or subtract value from any element of nums.
Example
- Input
- nums = [1,-10,7,13,6,8], value = 5
- Output
- 4
- Explanation
- One can achieve this result by applying the following operations:
Python solution
class Solution:
def findSmallestInteger(self, nums: List[int], value: int) -> int:
cnt = Counter(x % value for x in nums)
for i in range(len(nums) + 1):
if cnt[i % value] == 0:
return i
cnt[i % value] -= 1Complexity
- Time
- O(n)
- Space · auxiliary
- O(value)where n is the length of array nums
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 2598. Smallest Missing Non-negative Integer After Operations is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0781 | Rabbits in Forest | Medium |
| 2597 | The Number of Beautiful Subsets | Medium |
| 0149 | Max Points on a Line | Hard |
| 0268 | Missing Number | Easy |
| 0380 | Insert Delete GetRandom O(1) | Medium |
| 0381 | Insert Delete GetRandom O(1) - Duplicates allowed | Hard |
Frequently asked questions
- How hard is LeetCode 2598. Smallest Missing Non-negative Integer After Operations?
LeetCode 2598. Smallest Missing Non-negative Integer After Operations is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2598. Smallest Missing Non-negative Integer After Operations?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2598. Smallest Missing Non-negative Integer After Operations?
The Python solution on this page uses O(value), where n is the length of array \textit{nums} auxiliary space.
- What topics does LeetCode 2598. Smallest Missing Non-negative Integer After Operations cover?
LeetCode 2598. Smallest Missing Non-negative Integer After Operations is tagged Greedy, Array, Hash Table and Math on LeetCode.