Find kth missing integer and redundant operations

You are given two independent coding tasks.

Task 1: K-th missing number

You are given an integer array nums (not necessarily sorted) containing distinct positive integers, and an integer k.

Define the missing numbers as the positive integers that do not appear in nums.

Return the k-th smallest missing positive integer.

Constraints (representative of an “optimal required” setting):

• 1 <= n <= 2e5
• 1 <= nums[i] <= 1e9 (distinct)
• 1 <= k <= 1e9

Example:

• nums = [2, 3, 7, 11], k = 5
• Missing positives are 1, 4, 5, 6, 8, 9, 10, 12, ...
• Answer: 8

Task 2: Count redundant operations within a time window

You are given two arrays of equal length ops[] and times[] describing a log of events, where:

• ops[i] is a string operation name (e.g., "login", "refresh")
• times[i] is the event time as an integer timestamp (seconds)

You are also given an integer window size W (seconds).

An event at index i is considered redundant if there exist two earlier events j < k < i such that:

• ops[j] == ops[k] == ops[i]
• times[i] - times[j] <= W (i.e., 3 occurrences of the same operation happen within a W-second window ending at times[i])

Return the total number of redundant events in the log.

Assumptions/notes:

• The input may not be sorted; you may sort by time if needed.
• If multiple events share the same timestamp, treat earlier indices as earlier events.

Example:

• ops = ["A","B","A","A","A"], times = [1,2,3,4,10], W = 5
• The event at time 4 is redundant because A occurred at times 1,3,4 within 5 seconds.
• The event at time 10 is not redundant for window W=5.
• Answer: 1

Part 1: K-th Missing Positive Integer

You are given an array nums of distinct positive integers and an integer k. The array is not necessarily sorted. Consider all positive integers that do not appear in nums. Return the k-th smallest missing positive integer.

Your solution should be efficient enough for large inputs, so avoid generating missing numbers one by one.

Constraints

• 1 <= len(nums) <= 2 * 10^5
• 1 <= nums[i] <= 10^9
• All values in nums are distinct
• 1 <= k <= 10^9

Examples

Example 1

Input: ([2, 3, 7, 11], 5)
Output: 8

Explanation: After sorting, the missing positives are 1, 4, 5, 6, 8, 9, ... so the 5th missing value is 8.

Example 2

Input: ([5], 3)
Output: 3

Explanation: The missing positives begin as 1, 2, 3, 4, 6, ... so the 3rd missing value is 3.

Hints

1. Sort the numbers first so you can count how many positives are missing in each gap.
2. If there are gap = curr - prev - 1 missing values between two kept numbers, either the answer is inside that gap or you can skip the whole gap and reduce k.

Part 2: Count Redundant Operations Within a Time Window

You are given two arrays of equal length, ops and times, describing a log of events. ops[i] is the operation name and times[i] is its timestamp in seconds.

An event is considered redundant if there exist two earlier events of the same operation such that all three occurrences lie within a window of W seconds ending at the current event. In other words, an event at position i is redundant if there are indices j < k < i with ops[j] == ops[k] == ops[i] and times[i] - times[j] <= W.

The input may not be sorted by time. If multiple events have the same timestamp, the one with the smaller original index is considered earlier.

Constraints

• 1 <= len(ops) == len(times) <= 2 * 10^5
• 0 <= times[i] <= 10^9
• 0 <= W <= 10^9
• ops[i] is a non-empty string

Examples

Example 1

Input: (["A", "B", "A", "A", "A"], [1, 2, 3, 4, 10], 5)
Output: 1

Explanation: The A at time 4 is redundant because A appears at times 1, 3, and 4 within 5 seconds. The A at time 10 is not.

Example 2

Input: (["x", "x", "x", "x"], [5, 5, 5, 5], 0)
Output: 2

Explanation: With the same timestamp and W = 0, the 3rd and 4th events each have two earlier matching events within the window.

Hints

1. After ordering events by (time, original index), process them from earliest to latest.
2. For each operation name, keep only previous timestamps that are still within W seconds of the current event. The current event is redundant if at least two such timestamps remain.