LeetCode 3911 - K-th Smallest Remaining Even Integer in Subarray Queries

LeetCode Problem 3911

Difficulty: 🔴 Hard
Topics: Array, Binary Search

Solution

Problem Understanding

The problem provides a strictly increasing integer array nums and a list of queries, each consisting of [li, ri, ki]. For each query, we consider the subarray nums[li..ri] and remove all elements of this subarray from the infinite sequence of positive even integers. The task is to determine the kith smallest number remaining in that sequence.

The input guarantees that nums is strictly increasing, meaning there are no duplicates and the array is sorted. Each query may ask for a very large ki (up to $10^9$), and nums itself may contain up to $10^5$ elements. The problem requires careful handling of large ranges and efficient computation without explicitly generating the infinite sequence of even integers or removing numbers one by one, which would be infeasible.

Important edge cases include when nums contains even numbers, when ki is smaller than the first remaining even, and when subarrays remove multiple consecutive even numbers. The strict increase of nums simplifies some checks because each number is unique and ordered.

Approaches

The brute-force approach would attempt to generate the infinite sequence of even numbers, remove all numbers appearing in the subarray, and then pick the kith smallest. This is obviously infeasible because ki can be up to $10^9$, and removing elements from such a sequence would be extremely slow.

The optimal approach leverages the strictly increasing nature of nums and the structure of even numbers. The key insight is that for any integer x, the number of even integers less than or equal to x is simply x // 2. By also counting how many numbers in the subarray are even and ≤ x, we can determine how many even numbers remain ≤ x. This allows us to perform binary search over x to find the smallest x such that there are at least ki remaining even numbers.

By doing this, we avoid explicitly generating sequences and can answer each query efficiently in logarithmic time relative to the maximum possible integer, leveraging binary search.

Algorithm Walkthrough

1. Precompute a prefix sum array of even numbers in nums. Let even_prefix[i] represent the number of even numbers in nums[0..i]. This allows O(1) queries for the number of even numbers in any subarray.
2. For each query [li, ri, ki], perform a binary search on the answer x, which represents the value of the kith remaining even number.
3. Define a function count_remaining_evens(x, li, ri) that computes the number of even integers ≤ x remaining after removing nums[li..ri]. It is calculated as (x // 2) - (number of even numbers in nums[li..ri] ≤ x).
4. Use binary search over x starting from 2 to a sufficiently large upper bound (e.g., 2 * 10^9 + 2 * 10^5) to find the smallest x where count_remaining_evens(x, li, ri) >= ki.
5. The result of the binary search is the answer for that query. Repeat for all queries.

Why it works: Binary search works because count_remaining_evens(x, li, ri) is monotonically increasing with x. Once we reach a point where at least ki remaining even numbers exist, any larger x would also satisfy it. The smallest x found is exactly the kith remaining even number.

Python Solution

class Solution:
    def kthRemainingInteger(self, nums: list[int], queries: list[list[int]]) -> list[int]:
        n = len(nums)
        even_prefix = [0] * n
        even_prefix[0] = 1 if nums[0] % 2 == 0 else 0
        for i in range(1, n):
            even_prefix[i] = even_prefix[i - 1] + (1 if nums[i] % 2 == 0 else 0)

        def even_count_subarray(l, r, x):
            # Count even numbers in nums[l..r] that are <= x
            # Binary search for upper bound in nums[l..r]
            left, right = l, r
            pos = l - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] <= x:
                    pos = mid
                    left = mid + 1
                else:
                    right = mid - 1
            if pos < l:
                return 0
            return even_prefix[pos] - (even_prefix[l - 1] if l > 0 else 0)

        ans = []
        for li, ri, ki in queries:
            low, high = 2, 2 * (10**9 + 2 * 10**5)
            while low < high:
                mid = (low + high) // 2
                remaining = mid // 2 - even_count_subarray(li, ri, mid)
                if remaining >= ki:
                    high = mid
                else:
                    low = mid + 1
            ans.append(low)
        return ans

Implementation Walkthrough: We first precompute even_prefix to quickly count even numbers in any subarray. For each query, we define even_count_subarray using binary search to efficiently count how many even numbers in nums[li..ri] are ≤ a candidate x. We then binary search for the smallest x such that the number of remaining even numbers is at least ki. This avoids explicit sequence generation.

Go Solution

func kthRemainingInteger(nums []int, queries [][]int) []int {
    n := len(nums)
    evenPrefix := make([]int, n)
    if nums[0]%2 == 0 {
        evenPrefix[0] = 1
    }
    for i := 1; i < n; i++ {
        evenPrefix[i] = evenPrefix[i-1]
        if nums[i]%2 == 0 {
            evenPrefix[i]++
        }
    }

    countEvenSubarray := func(l, r, x int) int {
        pos := l - 1
        left, right := l, r
        for left <= right {
            mid := (left + right) / 2
            if nums[mid] <= x {
                pos = mid
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        if pos < l {
            return 0
        }
        res := evenPrefix[pos]
        if l > 0 {
            res -= evenPrefix[l-1]
        }
        return res
    }

    ans := make([]int, len(queries))
    for i, q := range queries {
        li, ri, ki := q[0], q[1], q[2]
        low, high := 2, 2*(1e9+2*1e5)
        for low < high {
            mid := (low + high) / 2
            remaining := mid/2 - countEvenSubarray(li, ri, mid)
            if remaining >= ki {
                high = mid
            } else {
                low = mid + 1
            }
        }
        ans[i] = low
    }
    return ans
}

Go-Specific Notes: Go handles slices efficiently, and integer arithmetic is naturally bounded by 64-bit ints. The logic is equivalent to Python, using slices and built-in integer arithmetic. No special handling is needed for empty arrays since constraints guarantee non-empty input.

Worked Examples

Example 1: nums = [1,4,7], queries = [[0,2,1],[1,1,2],[0,0,3]]

Example 2: nums = [2,5,8], queries = [[0,1,2],[1,2,1],[0,2,4]]