FastPrep
Problem · Array

Number of Unique Elements After Modifications 🍁

Learn this problem
● Mediuminfosys logoinfosysOA

Problem statement

You are given an integer array nums of length n and a list queries of length m. Process the queries in order. For each query [L, x]:

  1. Update nums[L - 1] = nums[L - 1] - x. Each update is applied to the array produced by all previous updates.
  2. Build an array B from the updated nums: set B[0] = nums[0], and for every 1 <= i < n, set B[i] = min(B[i - 1], nums[i]).

After each query, count the number of distinct values in B. Return these counts in order.

Function

getUniqueElementCounts(nums: int[], queries: int[][]) → int[]

Examples

Example 1

nums = [5, 7, 2, 2, 4]queries = [[2, 2], [5, 4]]return = [2, 3]

After query [2, 2], nums becomes [5, 5, 2, 2, 4]. Its prefix-minimum array is [5, 5, 2, 2, 2], which has 2 distinct values.

After query [5, 4], nums becomes [5, 5, 2, 2, 0]. Its prefix-minimum array is [5, 5, 2, 2, 0], which has 3 distinct values. Therefore the answer is [2, 3].

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= queries.length <= 10^5
  • 1 <= nums[i] <= 10^9 before any updates
  • Every query is [L, x] with 1 <= L <= nums.length and 1 <= x <= 10^5.

More infosys problems

drafts saved locally
public int[] getUniqueElementCounts(int[] nums, int[][] queries) {
    // write your code here
}
nums[5, 7, 2, 2, 4]
queries[[2, 2], [5, 4]]
expected[2, 3]
checking account