Collecting Numbers II

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
0 upvote
Asked in company
CIS - Cyber Infrastructure

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3 1 
2 1 3
2 3
3 2
3 2 1
1 3
1 2
Sample Output 1 :
2
1 2
Explanation of sample input 1 :
For the first test case, 
In the first operation, we will swap numbers at positions 2 and 3, and then the array will be [2, 3, 1]. We will collect 1 in the first round, and the array after the first round will be [2, 3]. Finally, we will collect 2 and 3 in the second round. Hence, the total number of rounds required is 2 in this case.

For the second test case,
In the first operation, we will swap numbers at positions 1 and 3, and then the array will be [1, 2, 3]. We will collect all numbers in the first round. Hence, the total number of rounds required is 1 in this case.
In the second operation, we will swap numbers at positions 1 and 2, then the array will be [2, 1, 3]. We will collect 1 in the first round, and the array after the first round will be [2, 3]. Finally, we will collect 2 and 3 in the second round. Hence, the total number of rounds required is 2 in this case.
Sample Input 2 :
2
5 2
4 2 1 5 3
2 3 
3 5
5 2
1 2 3 4 5
2 3
5 4
Sample Output 2 :
2 3
2 3
Hint

After performing each operation on the array, traverse through the input array in the described manner and collect as many numbers as possible in each round.

Approaches (3)
Brute Force

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.
    • Insert totalRounds in answer.
  • Return the array answer.
Time Complexity

O((N^2)*M), where N denotes the number of elements in the array ARR and  M is the number of queries.

 

We are doing M iterations, and in each iteration, it takes O(N^2) time to traverse through the array ARR to collect numbers. Hence, the overall Time Complexity is O((N^2)*M).

Space Complexity

O(1). 

 

Constant space is being used. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Collecting Numbers II
Full screen
Console