Find X Value of Array II

Hard

#3136Time: O(Q * N), where Q is the number of queries and N is the length of `nums`. For each of the Q queries, we might iterate through up to N elements.Space: O(N) to store the `nums` array. If we exclude the storage for input and output, the auxiliary space complexity is O(1).1 company

Patterns

Math

Data structures

Array Segment Tree

Companies

Rubrik

Prompt

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] = [index_i, value_i, start_i, x_i].

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 x_i after performing the following actions:

Update nums[index_i] to value_i. Only this step persists for the rest of the queries.
Remove the prefix nums[0..(start_i - 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 i^th 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:

For query 0, nums becomes [1, 2, 2, 4, 5], and the empty prefix must be removed. The possible operations are:
- Remove the suffix [2, 4, 5]. nums becomes [1, 2].
- Remove the empty suffix. nums becomes [1, 2, 2, 4, 5] with a product 80, which gives remainder 2 when divided by 3.
For query 1, nums becomes [1, 2, 2, 3, 5], and the prefix [1, 2, 2] must be removed. The possible operations are:
- Remove the empty suffix. nums becomes [3, 5].
- Remove the suffix [5]. nums becomes [3].
For query 2, nums becomes [1, 2, 2, 3, 5], and the empty prefix must be removed. The possible operations are:
- Remove the suffix [2, 2, 3, 5]. nums becomes [1].
- Remove the suffix [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:

For query 0, nums becomes [2, 2, 4, 8, 16, 32]. The only possible operation is:
- Remove the suffix [2, 4, 8, 16, 32].
For query 1, 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] <= 10⁹
1 <= nums.length <= 10⁵
1 <= k <= 5
1 <= queries.length <= 2 * 10⁴
queries[i] == [index_i, value_i, start_i, x_i]
0 <= index_i <= nums.length - 1
1 <= value_i <= 10⁹
0 <= start_i <= nums.length - 1
0 <= x_i <= k - 1

Approaches

2 approaches with complexity analysis and trade-offs.

For each query, we first perform the update on the nums array. Then, we simulate the process described in the problem. We iterate through all possible non-empty prefixes of the subarray nums[start...], calculate their product modulo k, and count how many of them are equal to the target x.

Algorithm

Initialize an empty list results.
For each query [index, value, start, x] in queries:
- Update nums[index] = value.
- Initialize count = 0 and current_product = 1.
- Iterate with j from start to nums.length - 1.
  - Update current_product = (current_product * nums[j]) % k.
  - If current_product == x, increment count.
- Append count to results.
Return results.

Walkthrough

This approach directly translates the problem statement into code. For every single query, it modifies the nums array and then iterates from the given start index to the end of the array. In this loop, it maintains a running product of the elements of the current prefix, takes it modulo k, and checks if it matches the query's x value. While straightforward, this method is computationally expensive because it re-calculates products for overlapping subproblems across different queries.

1class Solution {2    public int[] findXValue(int[] nums, int k, int[][] queries) {3        int[] result = new int[queries.length];4        long[] longNums = new long[nums.length];5        for (int i = 0; i < nums.length; i++) {6            longNums[i] = nums[i];7        }8 9        for (int i = 0; i < queries.length; i++) {10            int index = queries[i][0];11            int value = queries[i][1];12            int start = queries[i][2];13            int x = queries[i][3];14 15            longNums[index] = value;16 17            int count = 0;18            if (start < longNums.length) {19                long currentProduct = 1;20                for (int j = start; j < longNums.length; j++) {21                    currentProduct = (currentProduct * longNums[j]) % k;22                    if (currentProduct == x) {23                        count++;24                    }25                }26            }27            result[i] = count;28        }29        return result;30    }31}

Complexity

Time

O(Q * N), where Q is the number of queries and N is the length of `nums`. For each of the Q queries, we might iterate through up to N elements.

Space

O(N) to store the `nums` array. If we exclude the storage for input and output, the auxiliary space complexity is O(1).

Trade-offs

Pros

Simple to understand and implement.
Low memory overhead.

Cons

Highly inefficient due to re-computation for each query.
Will result in a 'Time Limit Exceeded' error for the given constraints.

A highly efficient approach using a Segment Tree data structure. Since queries involve point updates and range-like queries, a segment tree is a natural fit. The key is to design the segment tree nodes and the merge operation to handle the specific requirements of the problem, which involve prefix products modulo k.

Algorithm

Define a Node structure for the segment tree to store prod (product of elements in its range mod k) and counts (an array of size k for prefix product remainders).
Implement a merge function that combines two nodes. The new prod is the product of the children's prods. The new counts are the left child's counts plus the right child's counts transformed by left.prod.
Build: Construct the segment tree from the initial nums array in O(N*k) time.
For each query [index, value, start, x]:
- Update: Perform a point update on the segment tree for nums[index] = value. This takes O(k * log N).
- Query: Perform a range query on the segment tree for [start, N-1]. This also takes O(k * log N). The result is a Node representing the entire range.
- The answer to the query is result_node.counts[x].

Walkthrough

Each node in our segment tree will store two pieces of information for its corresponding range in the nums array:

prod: The total product of all elements in the range, modulo k.
counts: An array of size k. counts[r] stores the number of prefixes starting from the beginning of the node's range whose product modulo k is r.

The merge operation is crucial. When merging a left and right node, the new prod is simply (left.prod * right.prod) % k. The new counts array is formed by combining the left.counts with a transformed version of right.counts. Specifically, any prefix in the right child's range with product p contributes to a combined prefix with product (left.prod * p) % k. This allows us to efficiently calculate the required counts for any range.

An update changes a leaf and propagates up to the root by re-merging. A query for nums[start...] is a range query on the segment tree for [start, N-1], which efficiently combines nodes to get the final counts.

1class Solution {2    class Node {3        long prod;4        long[] counts;5 6        Node(int k) {7            this.prod = 1;8            this.counts = new long[k];9        }10    }11 12    int k;13    long[] nums;14    Node[] tree;15 16    private Node merge(Node left, Node right) {17        Node res = new Node(k);18        res.prod = (left.prod * right.prod) % k;19        for (int i = 0; i < k; i++) {20            res.counts[i] = left.counts[i];21        }22        for (int i = 0; i < k; i++) {23            if (right.counts[i] > 0) {24                int newRem = (int) ((left.prod * i) % k);25                res.counts[newRem] += right.counts[i];26            }27        }28        return res;29    }30 31    private void build(int node, int start, int end) {32        if (start == end) {33            tree[node] = new Node(k);34            tree[node].prod = nums[start] % k;35            tree[node].counts[(int)(nums[start] % k)] = 1;36            return;37        }38        int mid = start + (end - start) / 2;39        build(2 * node, start, mid);40        build(2 * node + 1, mid + 1, end);41        tree[node] = merge(tree[2 * node], tree[2 * node + 1]);42    }43 44    private void update(int node, int start, int end, int idx, long val) {45        if (start == end) {46            nums[idx] = val;47            tree[node] = new Node(k);48            tree[node].prod = val % k;49            tree[node].counts[(int)(val % k)] = 1;50            return;51        }52        int mid = start + (end - start) / 2;53        if (start <= idx && idx <= mid) {54            update(2 * node, start, mid, idx, val);55        } else {56            update(2 * node + 1, mid + 1, end, idx, val);57        }58        tree[node] = merge(tree[2 * node], tree[2 * node + 1]);59    }60 61    private Node query(int node, int start, int end, int l, int r) {62        if (r < start || end < l || l > r) {63            return new Node(k); // Identity node64        }65        if (l <= start && end <= r) {66            return tree[node];67        }68        int mid = start + (end - start) / 2;69        Node p1 = query(2 * node, start, mid, l, r);70        Node p2 = query(2 * node + 1, mid + 1, end, l, r);71        return merge(p1, p2);72    }73 74    public int[] findXValue(int[] initialNums, int k, int[][] queries) {75        this.k = k;76        int n = initialNums.length;77        this.nums = new long[n];78        for(int i=0; i<n; ++i) this.nums[i] = initialNums[i];79        80        this.tree = new Node[4 * n];81        build(1, 0, n - 1);82 83        int[] result = new int[queries.length];84        for (int i = 0; i < queries.length; i++) {85            int index = queries[i][0];86            int value = queries[i][1];87            int start = queries[i][2];88            int x = queries[i][3];89 90            update(1, 0, n - 1, index, value);91            92            if (start >= n) {93                result[i] = 0;94            } else {95                Node resNode = query(1, 0, n - 1, start, n - 1);96                result[i] = (int) resNode.counts[x];97            }98        }99        return result;100    }101}

Complexity

Time

O(N*k + Q * k * log N). Building the tree takes `O(N*k)`. Each of the Q queries involves an update and a query, both taking `O(k * log N)` time.

Space

O(N * k) to store the segment tree. Each of the `O(N)` nodes stores an array of size `k`.

Trade-offs

Pros

Very efficient for the given constraints.
Handles online updates and queries effectively with logarithmic time complexity per operation.

Cons

More complex to implement compared to the brute-force approach.
Higher constant factor in time complexity and uses more memory.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem