LeetCode 3524 & 3525: From a static to a dynamic solution

The main difference between LeetCode 3524. Find X Value of Array I and LeetCode 3525. Find X Value of Array II is that the second problem introduces dynamic updates.

3524. Find X Value of Array I

In 3524 problem, the nums array does not change. We need to count how many ways we can remove a prefix and a suffix while keeping the array non-empty so that:

product % k == x

Since the array is static, we can process it from left to right and maintain the number of products for each possible remainder:

0, 1, ..., k - 1

This is essentially Dynamic Programming over remainders + Modular Arithmetic technique, so we do not need to use a Segment Tree pattern.

Hence, we can solve a LeetCode 3524 problem using this technique:

static nums, then process elements once, then Dynamic Programming over remainders, and then get answer.

Complexity is:

Time: O(n * k)
Space: O(k)

Since k <= 5, this is effectively:

Time complexity: O(n)
Space complexity: O(1)

3525. Find X Value of Array II

In 3525 problem, we have multiple queries:

[index, value, start, x]

Each query first performs a permanent update:

nums[index] = value

The updated value remains in the array for all following queries.

After the update, we need to calculate the x-value for:

nums[start ... n - 1]

So now we have a dynamic sequence of operations:

nums - point update - query [start, n - 1] - point update - query [start, n - 1] - ...

If we simply ran the 3524 algorithm again after every update, the complexity would be approximately O(q * n * k) - which is too slow.

Instead, 3525 problem uses a Segment Tree pattern. Each node stores:

prod
cnt[0 ... k - 1]

Here, prod is the product of the entire segment modulo k, while cnt[r] stores the number of non-empty prefixes whose product has remainder r.

This allows us to perform update nums[index] it O(k * log n) time and query [start, n - 1] in O(k * log n) time.

The total complexity is O(n * k + q * k * log n).
Since k <= 5 we have O(n + q * log n).

Time complexity: O(n + q * k * log n) = O(n + q * log n)
Space complexity: O(n * k) = O(n)

where q is the number of queries.

In short, LeetCode 3525 problem is the dynamic version of the idea used in LeetCode 3524 problem. The remainder-counting idea is still the same, but because the array changes after every query, we need a Segment Tree patern to update and recompute only the affected parts efficiently.

LeetCode 3524 C++ solution

class Solution {
public:
  vector<long long> resultArray(vector<int>& nums, int k) {
    vector<long long> result(k, 0);
    vector<long long> dp(k, 0);

    for(int num : nums)
    {
      vector<long long> next(k, 0);
      int value = num % k;

      // Start a new subarray.
      next[value]++;

      // Extend all subarrays ending at the previous position.
      for(int r = 0; r < k; r++)
      {
        int newRemainder = (r * value) % k;
        next[newRemainder] += dp[r];
      }

      for(int r = 0; r < k; r++) result[r] += next[r];

      dp = move(next);
    }

    return result;
  }
};

LeetCode 3525 C++ solution

class Solution {
  // Each node stores the product of the whole segment modulo k
  // and the number of prefixes for every possible remainder.
  struct Node {
    int prod = 1;
    array<int, 5> cnt{};
  };

  int n, k;
  vector<Node> tree;

  // Merge two adjacent segments.
  // Keep all prefixes from the left segment.
  // Prefixes from the right segment are multiplied by the full left product.
  Node mergeNodes(const Node& left, const Node& right) {
    Node res;
    res.prod = (left.prod * right.prod) % k;

    for(int r = 0; r < k; r++) res.cnt[r] += left.cnt[r];

    for(int r = 0; r < k; r++) {
      int nr = (left.prod * r) % k;
      res.cnt[nr] += right.cnt[r];
    }

    return res;
  }

  // Build the segment tree.
  // A leaf has exactly one non-empty prefix: the element itself.
  void build(int node, int l, int r, const vector<int>& nums) {
    if(l == r) {
      int rem = nums[l] % k;
      tree[node].prod = rem;
      tree[node].cnt[rem] = 1;

      return;
    }

    int mid = l + (r - l) / 2;

    build(node * 2, l, mid, nums);
    build(node * 2 + 1, mid + 1, r, nums);

    tree[node] = mergeNodes(tree[node * 2], tree[node * 2 + 1]);
  }

    // Permanently update nums[index] and rebuild the affected tree nodes.
  void update(int node, int l, int r, int index, int value) {
    if(l == r) {
      tree[node] = Node{};

      int rem = value % k;
      tree[node].prod = rem;
      tree[node].cnt[rem] = 1;

      return;
    }

    int mid = l + (r - l) / 2;

    if(index <= mid) update(node * 2, l, mid, index, value);
    else update(node * 2 + 1, mid + 1, r, index, value);

    tree[node] = mergeNodes(tree[node * 2], tree[node * 2 + 1]);
  }

  // Return the combined information for range [ql, qr].
  // For each query this range is [start, n - 1].
  Node query(int node, int l, int r, int ql, int qr) {
    if(ql <= l && r <= qr) return tree[node];

    int mid = l + (r - l) / 2;

    if(qr <= mid) return query(node * 2, l, mid, ql, qr);
    if(ql > mid) return query(node * 2 + 1, mid + 1, r, ql, qr);

    Node left = query(node * 2, l, mid, ql, qr);
    Node right = query(node * 2 + 1, mid + 1, r, ql, qr);

    return mergeNodes(left, right);
  }

public:
  vector<int> resultArray(vector<int>& nums, int k, vector<vector<int>>& queries) {
    this->n = nums.size();
    this->k = k;

    // Build the tree for the initial array.
    tree.resize(4 * n);
    build(1, 0, n - 1, nums);

    vector<int> result;
    result.reserve(queries.size());

    // Apply each permanent update, then analyze nums[start..n - 1].
    for(const auto& q : queries) {
      int index = q[0];
      int value = q[1];
      int start = q[2];
      int x = q[3];

      update(1, 0, n - 1, index, value);

      // cnt[x] is the number of prefixes of nums[start..n - 1]
      // whose product modulo k equals x.
      Node res = query(1, 0, n - 1, start, n - 1);
      result.push_back(res.cnt[x]);
    }

    return result;
  }
};