Sort The Tuples

Easy
0/40
Average time to solve is 15m
profile
Contributed by
9 upvotes

Problem statement

You are given an array of tuples ‘ARR’ of length ‘N’. All the tuples are of length ‘L’. Sort the tuples in non-decreasing order by the last element of tuples. If the last element of two tuples are equal then the tuple with the smallest index should be placed first.

Note: The length of all the tuples will be the same.

Example: 
Input: ‘N’ = 3, ‘L’ = 2,  ‘ARR’ = [(1, 1), (5, 3), (8, 2)]. 

Output: [(1, 1), (8, 2), (5, 3)].

The last values of each type are (1, 3, 2). Sorting them in non-decreasing order we get (1, 2, 3). Hence the final result is [(1, 1), (8, 2), (5, 3)].
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains two integers ‘N’ and ‘L’  where ‘N’ denotes the length of the array ‘NUMS’ and ‘L’ denotes the length of the tuples.

The next ‘N’ lines of each test case contain ‘N’ tuples of integers.
Output format : 
For each test case, you don’t need to return anything just return the resultant array.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^5
Sum of total number of integers <= 10^5
1 <= ARR[i].length <= 1000

Time Limit: 1 sec
Sample Input 1 :
2
4 2
1 2
1 1
3 5
2 3
4 3
1 2 3
3 2 1
4 5 6
3 1 2
Sample Output 1 :
1 1 
1 2 
2 3 
3 5 
3 2 1 
3 1 2 
1 2 3 
4 5 6
Explanation Of Sample Input 1 :
For the first case:
The last elements of the tuples are [2, 1, 5, 3]. Sorting them in non-decreasing order we get [1, 2, 3, 5]. So, the final output is [ (1, 1), (1, 2), (2, 3), (3, 5) ].

For the second case:
The last elements of the tuples are [3, 1, 6, 2]. Sorting them in non-decreasing order we get [1, 2, 3, 6]. So, the final output is [ (3, 2, 1), (3, 1, 2), (1, 2, 3), (4, 5, 6) ].
Sample Input 2 :
2
1 4
1 4 5 7
3 4
7 81 2 10
1 2 4 1
90 28 2 19
Sample Output 2 :
1 4 5 7
1 2 4 1
7 81 2 10
90 28 2 19
Hint

Can you think of any way to sort the array using swap operations?

Approaches (2)
Bubble Sort

In the naive approach, we can use bubble sort. Iterate over each element of the array then run a second loop from the starting element and swap the adjacent tuples if the last element of the first tuple is greater than the last element of the second tuple.

 

The steps are as follows:-

Function sortTuples(vector<vector<int>>& arr):

  1. Run a loop from 'i'=0 to 'N' -1:
    • Run a loop from 'j' = 'i'+1 to 'N'-‘i'-2:
      • If the last element of 'j'th tuple is greater than the last element of the 'j'+1th tuple then swap the tuples.
Time Complexity

O( N^2 * L), Where ‘N’ denotes the number of tuples and ‘L’ denotes the length of the tuples.  

 

We are running two nested loops and the time complexity for swapping two tuples is O( L ), So the total time complexity is O( N^2 * L).

Hence the time complexity is O( N^2 * L ).

Space Complexity

O( L ), where ‘L’ denotes the length of the tuples.

 

The swapping of twp tuples has a space complexity of O( L ),

Hence space complexity is O( L ).

Code Solution
(100% EXP penalty)
Sort The Tuples
Full screen
Console