Last Updated: 25 Apr, 2021
Collecting Numbers II
Moderate
Asked in company
You are given an array ‘ARR’ of size ‘N’ containing each number between 1 and ‘N’ exactly once. On each round, you can traverse through the array ‘ARR’ from left to right and collect as many numbers as possible in increasing order. You are given ‘M’ operations in a 2-dimensional array ‘Queries’, in which Queries[i] contains two positions of the array ‘ARR’, whose values need to be swapped. The operations are performed one by one in the given order. Your task is to find the total number of rounds required to collect all the numbers from 1 to ‘N’ in increasing order after each operation.
For example :
Consider ARR = [4, 5, 1, 2, 3] and Queries=[[2, 3]], in the first operation, we will swap numbers at positions 2 and 3, then the array will be [4, 1, 5, 2, 3]. We will collect 1, 2, and 3 in the first round, and the array after the first round will be [4, 5]. Finally, we will collect 4 and 5 in the second round. Hence, the total number of rounds required is 2 in this case.
Input Format :
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains two space-separated integers, 'N' and ‘M’, denoting the number of elements in the array 'ARR', and the number of operations to be performed, respectively.
The second line of each test case contains 'N' space-separated integers denoting the elements of the array 'ARR'.
The Next 'M' lines of each test case contain two space-separated integers denoting the elements of the array ‘Queries’.
Output Format :
For each test case, print ‘M’ space-separated integers - the total number of rounds required to collect the numbers from 1 to ‘N’, in increasing order after each operation.
Print the output of each test case in a separate line.
Constraints :
1 <= T <= 10
1 <= N <= 10^5
1 <= ARR[i] <= N
1 <= Queries[i][0], Queries[i][1] <= N
All elements present in the array ARR are unique.
Queries[i][0] is not equal to Queries[i][1].
Where 'T' denotes the number of test cases, 'N' denotes the number of elements in the array, 'ARR[i]' denotes the 'i'th' element of the array 'ARR' and 'Queries[i]' is a tuple of two positions of the array ‘ARR’, whose numbers are needed to be swapped.
Time limit: 1 sec
Approaches
A simple method is to perform the operation by swapping the numbers present at the given two positions and traversing through the array ARR on each round until we have collected all numbers from 1 to N in increasing order.
To obtain the total number of rounds after each operation, we will maintain a variable currentNumber, which stores the element’s value, which we are trying to collect from the ARR. On each round, we will iterate index from 0 to N-1, and we will check if ARR[index] is equal to currentNumber, then we will increment currentNumber by 1. After each round, we will check if all numbers are collected. If all numbers are not collected from the ARR, then we will perform another round.
Algorithm:
- Create an array answer, which stores the total number of rounds required to collect all numbers from 1 to N after each operation.
- Iterate pos from 0 to M-1,
- Swap the numbers present at positions Queries[pos][0]-1 and Queries[pos][1]-1 in the array ARR.
- We will set totalRounds as 0. The variable totalRounds stores the total number of rounds required to collect all numbers from 1 to N.
- We will set the variable currentNumber as 1. The variable currentNumber stores the value of the number, which we are trying to collect from the ARR.
- Iterate till currentNumber is less than or equal to N,
- Iterate index till 0 to N-1,
- We will check if ARR[index] is equal to currentNumber, then we will Increment currentNumber by 1.
- Increment totalRounds by 1.
- Iterate index till 0 to N-1,
- Insert totalRounds in answer.
- Return the array answer.
The idea is to observe the fact that whenever the number val occurs before val+1, we can always take both of them in a single round, but if val comes after val+1, we cannot take them in the single round, and we will need to make an extra round to collect val+1. We will use this idea to find the total number of rounds to collect all numbers.
Our approach will be to construct array positions, which will store the index of all elements in the array ARR. For each query, we will perform the operation by swapping the numbers present at the given two positions and update the index of the value placed at both positions in the array positions. We will iterate currentNumber from 2 to N and we will find the index of currentNumber and currentNumber-1 with the help of the array positions. Now, there will be two cases,
- If the index of currentNumber is greater than the index of currentNumber-1, then we can collect both numbers in a single round.
- If the index of currentNumber is smaller than the index of currentNumber-1, then we cannot collect both numbers in a single round. We need to make an extra round to collect currentNumber. So, we will increment the total number of rounds by 1.
Algorithm:
- Create an array answer, which stores the total number of rounds required to collect all numbers from 1 to N after each operation.
- Create array positions of size N+1, which will store the index of all elements present in the array ARR.
- Iterate index from 0 to N-1,
- Assign the ARR[index] into the array positions with index+1 as its value.
- Iterate pos from 0 to M-1,
- Swap the numbers present at positions Queries[pos][0]-1 and Queries[pos][1]-1 in the array ARR and update the index of the value placed at both positions in the array positions.
- We will set totalRounds as 1. The variable totalRounds stores the total number of rounds required to collect all numbers from 1 to N.
- Iterate currentNumber from 2 to N,
- Check if the index of currentNumber is less than currentNumber-1,
- Increment totalRounds by 1.
- Check if the index of currentNumber is less than currentNumber-1,
- Insert totalRounds in answer.
- Return the array answer.
As we have discussed in the previous approach, for each value val in the array ARR, we are considering two pairs, i.e, (val-1, val) and (val, val+1). If the index of the first value is greater than the index of the second value, then we need to make an extra round to collect numbers from the second value.
Our approach will be to construct array positions, which will store the index of all elements in the array ARR. We will find the total number of rounds of the current permutation using the same approach used in the previous approach. For each query, we are swapping two numbers placed at positions x and y. We need to consider four pairs to find the total rounds of the modified permutation. The four pairs are (ARR[x] - 1, ARR[x]), (ARR[x], ARR[x] + 1), (ARR[y] - 1, ARR[y]) and (ARR[y], ARR[y] + 1). Our approach will be to decrement the total number of rounds of the current permutation by the number of pairs having an index of the first value greater than the second value. Then we will swap the numbers placed at the positions x and y, and we will update the index of the number placed at x and y in the array positions. Finally, we will increment the total number of rounds by the number of pairs following the given conditions to obtain the total number of rounds of the modified permutation. Note that we will consider each pair no more than once to avoid duplicate values.
Algorithm:
- Create an array answer, which stores the total number of rounds required to collect all numbers from 1 to N after each operation.
- We will set totalRounds as 1. The variable totalRounds stores the total number of rounds required to collect all numbers from 1 to N.
- Create array positions of size N+2, which will store the index of all elements present in the array ARR.
- Set positions[0] as 0 and positions[N+1] as N+1. We are doing this to consider pairs involving values 1 and N.
- Iterate index from 0 to N-1,
- Assign the ARR[index] into the array positions with index+1 as its value.
- Iterate currentNumber from 2 to N,
- Check if the index of currentNumber is less than currentNumber-1,
- Increment totalRounds by 1.
- Check if the index of currentNumber is less than currentNumber-1,
- Iterate pos from 0 to M-1,
- The variables firstValue and secondValue stores the value places at Queries[pos][0]-1 and Queries[pos][1]-1 in the array ARR.
- Check if positions[firstValue-1] is greater than positions[firstValue],
- Decrement totalRounds by 1.
- Check if positions[firstValue] is greater than positions[firstValue+1],
- Decrement totalRounds by 1.
- Check if secondValue-1 is not equal to firstValue and positions[secondValue-1] is greater than positions[secondValue],
- Decrement totalRounds by 1.
- Check if secondValue+1 is not equal to firstValue and positions[secondValue] is greater than positions[secondValue+1],
- Decrement totalRounds by 1.
- Swap the numbers present at positions Queries[pos][0]-1 and Queries[pos][1]-1 in the array ARR and update the index of firstValue and secondValue in the array positions.
- Apply similar conditions to increase totalRounds as we have used while decreasing totalRounds.
- Insert totalRounds in answer.
- Return the array answer.