FastPrepMinimum Swaps to Sort a Ternary Array After Updates
Problem · Array

Minimum Swaps to Sort a Ternary Array After Updates

Learn this problem
● HardGoogle logoGoogleINTERNOA
See Google hiring insights

Problem statement

You are given an integer array nums containing only 1, 2, and 3, together with a sequence of point-update queries.

Each query is [position, value]:

  • position is a one-based index into nums.
  • value is the new value assigned at that position.

Apply the queries cumulatively in their given order. After each update, find the minimum number of swaps required to sort the entire current array in nondecreasing order. One swap may exchange the values at any two positions.

Return an array containing one minimum-swap count for each query.

Function

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

Examples

Example 1

nums = [1,3,2]queries = [[2,2],[1,3]]return = [0,1]

After the first update, the array is [1, 2, 2], which is already sorted. After the second update, it is [3, 2, 2]; swapping the first and third positions produces [2, 2, 3].

Example 2

nums = [3,2,1,3,2,1]queries = [[3,3],[6,2],[1,1]]return = [2,2,2]

Each update changes the segment boundaries of the sorted target array. In all three resulting arrays, two arbitrary-position swaps are necessary and sufficient.

Example 3

nums = [2,1,3,1]queries = [[4,3],[3,2],[1,1]]return = [1,1,0]

The first two updated arrays each need one swap. The final update produces [1, 1, 2, 3], so its answer is 0.

Constraints

  • 1 <= nums.length <= 10^5.
  • 1 <= queries.length <= 10^5.
  • Every value in nums is 1, 2, or 3.
  • Every query contains exactly two integers [position, value].
  • 1 <= position <= nums.length.
  • value is 1, 2, or 3.

More Google problems

drafts saved locally
public int[] minimumSwapsAfterUpdates(int[] nums, int[][] queries) {
  // write your code here
}
nums[1,3,2]
queries[[2,2],[1,3]]
expected[0,1]
checking account