Watch 2 video solutions for Find X Value of Array II, a hard level problem involving Array, Math, Segment Tree. This walkthrough by Programming Live with Larry has 503 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array of positive integers nums and a positive integer k. You are also given a 2D array queries, where queries[i] = [indexi, valuei, starti, xi].
You are allowed to perform an operation once on nums, where you can remove any suffix from nums such that nums remains non-empty.
The x-value of nums for a given x is defined as the number of ways to perform this operation so that the product of the remaining elements leaves a remainder of x modulo k.
For each query in queries you need to determine the x-value of nums for xi after performing the following actions:
nums[indexi] to valuei. Only this step persists for the rest of the queries.nums[0..(starti - 1)] (where nums[0..(-1)] will be used to represent the empty prefix).Return an array result of size queries.length where result[i] is the answer for the ith query.
A prefix of an array is a subarray that starts from the beginning of the array and extends to any point within it.
A suffix of an array is a subarray that starts at any point within the array and extends to the end of the array.
Note that the prefix and suffix to be chosen for the operation can be empty.
Note that x-value has a different definition in this version.
Example 1:
Input: nums = [1,2,3,4,5], k = 3, queries = [[2,2,0,2],[3,3,3,0],[0,1,0,1]]
Output: [2,2,2]
Explanation:
nums becomes [1, 2, 2, 4, 5], and the empty prefix must be removed. The possible operations are:
[2, 4, 5]. nums becomes [1, 2].nums becomes [1, 2, 2, 4, 5] with a product 80, which gives remainder 2 when divided by 3.nums becomes [1, 2, 2, 3, 5], and the prefix [1, 2, 2] must be removed. The possible operations are:
nums becomes [3, 5].[5]. nums becomes [3].nums becomes [1, 2, 2, 3, 5], and the empty prefix must be removed. The possible operations are:
[2, 2, 3, 5]. nums becomes [1].[3, 5]. nums becomes [1, 2, 2].Example 2:
Input: nums = [1,2,4,8,16,32], k = 4, queries = [[0,2,0,2],[0,2,0,1]]
Output: [1,0]
Explanation:
nums becomes [2, 2, 4, 8, 16, 32]. The only possible operation is:
[2, 4, 8, 16, 32].nums becomes [2, 2, 4, 8, 16, 32]. There is no possible way to perform the operation.Example 3:
Input: nums = [1,1,2,1,1], k = 2, queries = [[2,1,0,1]]
Output: [5]
Constraints:
1 <= nums[i] <= 1091 <= nums.length <= 1051 <= k <= 51 <= queries.length <= 2 * 104queries[i] == [indexi, valuei, starti, xi]0 <= indexi <= nums.length - 11 <= valuei <= 1090 <= starti <= nums.length - 10 <= xi <= k - 1Problem Overview: You are given an array and must compute the array's X value, which depends on pairwise relationships between elements. The challenge becomes harder because the array changes over time, so you must update values and recompute the X metric efficiently without recalculating every pair from scratch.
Approach 1: Brute Force Pair Enumeration (O(n²) time, O(1) space)
The most direct solution recomputes the X value by iterating over every pair of indices (i, j) with i < j. For each pair, compute the contribution defined by the problem’s formula and add it to the running total. This guarantees correctness but becomes impractical for large arrays because each update forces a full recomputation. With n elements, the pair count grows to n(n-1)/2, leading to quadratic time. This approach mainly helps verify correctness during initial implementation.
Approach 2: Sorted Structure + Prefix Math (O(n log n) time, O(n) space)
Instead of recomputing every pair, maintain elements in sorted order and track prefix aggregates such as counts and sums. When processing an element, you can compute its total contribution against previously processed elements using mathematical relationships rather than explicit pair iteration. Binary search or balanced structures keep the array ordered, while prefix sums quickly calculate aggregated differences. This reduces repeated work and converts many pair operations into constant-time arithmetic. The main cost comes from maintaining order during updates.
Approach 3: Segment Tree with Frequency and Sum Tracking (O(n log n) time, O(n) space)
The scalable solution uses a segment tree indexed by value range. Each node stores two pieces of information: the number of elements in that range and the sum of those elements. When inserting or updating a value, query the tree to compute how many elements are smaller or larger and the total of those groups. Using these aggregates, you derive the element’s total contribution to the X value in logarithmic time. Updates simply adjust the counts and sums along the tree path. This approach combines array processing with mathematical aggregation, keeping every operation at O(log n).
Recommended for interviews: Start by explaining the brute force pair enumeration to show you understand how the X value is derived. Then transition to the segment tree solution. Interviewers expect you to recognize that repeated pair recomputation is too slow and replace it with aggregated counts and sums stored in a tree structure, reducing each update or query to logarithmic time.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Enumeration | O(n²) | O(1) | Small arrays or validating correctness during early development |
| Sorted Structure with Prefix Aggregates | O(n log n) | O(n) | When pair contributions can be expressed using prefix sums after sorting |
| Segment Tree with Count and Sum | O(n log n) | O(n) | Best for dynamic arrays with updates and repeated X value queries |