Company: Google_5july
Difficulty: medium
Sort the array Problem Description You are given an integer array A of size N containing only 1, 2, and 3. You are also given an integer Q and a 2D array of queries. You have to answer Q queries: For the i th query, perform A[queries[i][0]] = queries[i][1] and determine the minimum number of swaps required to sort the array in non-decreasing order. Task: For each query, determine the minimum swaps required to sort the array in non-decreasing order. Note: Array A and queries follow 0-based indexing. Examples Example 1: Input: 1 5 2 2 1 1 3 1 0 3 Output: 2 Explanation: The first line contains the number of test cases, T = 1. The first test case: Given: N = 5 A = [2, 2, 1, 1, 3] Q = 1 queries = [[0, 3]] Approach: Original A: [2, 2, 1, 1, 3] After the first update (A[0] = 3), the array A becomes [3, 2, 1, 1, 3]. To sort [3, 2, 1, 1, 3] into [1, 1, 2, 3, 3]: Swap indices 0 and 3: [1, 2, 1, 3, 3] Swap indices 1 and 2: [1, 1, 2, 3, 3] The minimum swaps required would be 2. Example 2: Input: N