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(\textit{value}), where n is the length of array \textit{nums} auxiliary space.

Smallest Missing Non-negative Integer After Operations — LeetCode 2598 Python Solution

MediumGreedyArrayHash TableMath

Problem: #2598
Pattern: Greedy
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

Python

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] -= 1

Complexity

Measure	Complexity
Time	O(n)
Space	O(\textit{value}), where n is the length of array \textit{nums} auxiliary

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.

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(\textit{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.