algorithm_DSA/!9. Nearly sorted - v5.py at main · AntoDB/algorithm_DSA · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#User function Template for python3

class Solution:

    #Function to return the sorted array.
    def nearlySorted(self,a,n,k):
        # code here
        sorted_list = [a.pop()]
        for i in range(len(a)):
            elm = a.pop(0)
            #print(elm)
            for index, sorted_elm in enumerate(sorted_list):
                #print(f'{index} : {sorted_elm}')
                if elm < sorted_elm:
                    sorted_list[index:index] = [elm]
                    #print(f'add : {sorted_list}')
                    break
                elif sorted_list[-1] < elm:
                    sorted_list.append(elm)
                    #print(f'add : {sorted_list}')
                    break
        #print(sorted_list)
        return sorted_list

#{
 # Driver Code Starts
#Initial Template for Python 3
import atexit
import io
import sys
import heapq
from collections import  defaultdict

# Contributed by : Nagendra Jha

if __name__ == '__main__':
    test_cases = int(input())
    for cases in range(test_cases) :
        n,k = map(int,input().strip().split())
        a = list(map(int,input().strip().split()))
        ob=Solution()
        print(*ob.nearlySorted(a,n,k))

# } Driver Code Ends


# Tested inputs :
'''
1
6 4
1 3 5 6 4 2
'''