Minimum Swaps to Sort a Ternary Array After Updates
Updated
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]:
positionis a one-based index intonums.valueis 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
numsis1,2, or3. - Every query contains exactly two integers
[position, value]. 1 <= position <= nums.length.valueis1,2, or3.
More Google Online Assessment questions
- Book Reading EveningsOA · Seen Nov 2026
- Count Score CategoriesOA · Seen Nov 2026
- Minimum Cars for Rental RequestsOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Shortest Path in a Binary MatrixOA · Seen Nov 2026
- Robot Assembly Line ConflictsOA · Seen Oct 2026
- Assign LockerOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Biggest Number From DigitsOA · Seen Oct 2026
- Consolidate On-Call RotationsOA · PHONE SCREEN · Seen Oct 2026
- Decreasing SubsequencesOA · Seen Sep 2026
- Minimize Absolute Difference of Server LoadsOA · Seen Sep 2026
Similar questions at other companies
- Most Items Within Budget from a Start IndexHudson River Trading · OAHudson River Trading interview questions
- Rebuild the Queue From Taller-in-Front CountsAdobe · PHONE SCREENAdobe interview questions
- Maximize K-Element AND with an Increment BudgetAmazon · OA
- Delete and Freeze GameRubrik · OARubrik interview questions
- Most Segments That Sort the ArrayRippling · OARippling interview questions
- Luna and the Colorful SocksPhonePe · OAPhonePe interview questions
- Minimum Starting Coins to Buy All ProductsMicrosoft · OAMicrosoft interview questions
- Get Max EfficiencySalesforce · OASalesforce interview questions
- Finding a Hidden Benchmark ValueSamsung · OASamsung interview questions
- Catch Fish with Reusable BaitsSusquehanna International Group (SIG) · OASusquehanna International Group (SIG) interview questions