4 Sort a K Sorted Array | Sort Nearly Sorted Array

Given an array of n elements, where each element is at most k away from its target position, devise an algorithm that sorts in O(n log k) time. For example, let us consider k is 2, an element at index 7 in the sorted array, can be at indexes 5, 6, 7, 8, 9 in the given array.
Input : arr[] = {6, 5, 3, 2, 8, 10, 9}
k = 3
Output : arr[] = {2, 3, 5, 6, 8, 9, 10}


  • keta mehta
    keta mehta4 天 前

    can we use sliding window for this question? for window size=k find smallest element

  • Hasan Said
    Hasan Said20 天 前

    Hey you always have the best videos but do you have this problem in English translation? lol i tried watching this one but idk you're language, no disrespect.

  • Kalpeshk B
    Kalpeshk B2 个月 前

    JAVA CODE : public ArrayList findKthLargest(int[ ] arr, int k) { PriorityQueue minHeap=new PriorityQueue(); ArrayList ans=new ArrayList(); for(int x:arr){ minHeap.add(x); if(minHeap.size()>k) ans.add(minHeap.poll()); } while(minHeap.size()>0){ ans.add(minHeap.poll()); } return ans; }

  • Shahana Alam
    Shahana Alam3 个月 前

    Awesome explanation bhiya 😄😄 Just keep up the good work!!

  • Nikhil Kumar
    Nikhil Kumar4 个月 前

    sir aap kahan tthe aaj tak. Thanks a lot.

    JUST FOR FUN4 个月 前

    Great explanation!

  • j k
    j k4 个月 前

    looking more such interview series from you .. great !

  • Atharv Sakhala
    Atharv Sakhala4 个月 前

    can you exaplin why it is n log k please?

  • Shahana Alam

    Shahana Alam

    3 个月 前

    Because we are comparing (sorting) only k elements at a time

  • Atharv Sakhala
    Atharv Sakhala4 个月 前

    can you still do this if k is unknown?

  • Yeeroj Sinha
    Yeeroj Sinha4 个月 前

    Bro i-k to i+k ,,,,,,so stack size should be 2k na????????????????????????

  • Aditya Raj

    Aditya Raj

    个月 前

    Teetar ke do aage teetar, teetar ke do peeche teetar, bolo kitne teetar? --- Teen, not paanch Similarly, heap size should be k, not 2k.

  • Amit Kumar

    Amit Kumar

    2 个月 前

    @Hunter Boi bro can u help me with the code

  • Hunter Boi

    Hunter Boi

    4 个月 前

    No bro !....i-k to i+k is the region in which we will find the sorted element. Size of the stack will be k as we go on popping the elements when it reaches k

  • TUTOR 247
    TUTOR 2475 个月 前

    #include #include using namespace std; int main() { //priority_queue Q; priority_queue Q; int n,k; cin>>n>>k; int a[n]; for(int i=0;i>a[i]; for(int i=0;ik) { a[i-k]=Q.top(); Q.pop(); } } for(int i=0;i

  • manas karlekar
    manas karlekar5 个月 前

    #include #include #include int sortK(int arr[], int n, int k) { std::priority_queue pq(arr,arr+k+1); int index = 0;// for the new array where the final answer is stored. for(int i=k+1;i

  • manas karlekar
    manas karlekar5 个月 前

    Is using STL/ STANDARD LIBRARY and PRIORITY QUEUE acceptable in coding rounds ???? The idea of understanding the implementation part of some of the tough algorithms scares the shit out of me !! :( expecting replies from the IT and software professionals .....

  • Yeeroj Sinha

    Yeeroj Sinha

    4 个月 前

    Yes STL is allowed

    ASHISH YADAV5 个月 前

    Awesome bro

  • Rashika Chopra
    Rashika Chopra5 个月 前

    If k is 2 then the first value will be 3 instead of 2. Kindly cover this case!!!

  • Hunting Nirvana

    Hunting Nirvana

    5 个月 前

    I think if K is changed, so will the Input array. The input array in this question is designed for k=3.

  • Monil Dand
    Monil Dand6 个月 前

    Sir, please tell how to implement heap in java.

  • EK HunterZ

    EK HunterZ

    13 天 前

    @DINESH KUMAR why you pass Collections.reverseOrder() inside the constructor of priorityQueue ?



    5 个月 前

    For MinHeap use PriorityQueueminH = new PriorityQueue(); For MaxHeap use PriorityQueuemaxH = new PriorityQueue(Collections.reverseOrder());

  • Debashish Nanda
    Debashish Nanda6 个月 前

    can you explain the question of trapping rainwater II based on minHeap - leetcode.com/problems/trapping-rain-water-ii/

  • Kavish Ramchandani
    Kavish Ramchandani6 个月 前

    Can we do this questions in O(1) space complexity??



    6 个月 前

    yup,with insertion sort with timr complexity O(n*k)

  • divyesh srivastava
    divyesh srivastava6 个月 前

    Nice explaination !!


    Thank you 😊


    Great explaination by u😊😊

  • vibhor Agarwal
    vibhor Agarwal7 个月 前

    Excellent Explanation!!!! totally out of context question Bro are you from UP??

  • Aditya Raj

    Aditya Raj

    个月 前

    MP, most probably. UP people don't say "Hum" as "Uppan".

  • divyesh srivastava

    divyesh srivastava

    6 个月 前

    Bareily sa hain

    MUKUL BAKSHI7 个月 前

    Bro very Nice Tutorial. Love the way you explain and share knowledge. I am looking in heap question, Please can you make a video on this question of the Heap leetcode.com/discuss/interview-question/542597/ I don't know how to apply your same technique here that you teach on the heap. Please help in this one, I will be thankful to you.

  • Pushpender Sharma

    Pushpender Sharma

    3 个月 前

    Heap can we used to sort the Map by value in Java if you are using Priority Queue

  • keerthi reddy
    keerthi reddy7 个月 前

    Thank you so much bro for this valuable content.so happy to learn

  • Sarthak Bhatia
    Sarthak Bhatia8 个月 前

    #include #include #include using namespace std; void sort_nearly_sorted(int *arr, int n, int k) { priority_queue p; int j = 0; for (int i = 0; i { p.push(arr[i]); if (p.size() > k) { arr[j] = p.top(); p.pop(); ++j; } } while (p.size() > 0) { arr[j] = p.top(); p.pop(); ++j; } } void print_Arr(int arr[], int n) { for (int i = 0; i cout

  • Sk m
    Sk m8 个月 前

    bro code ka video hai?

  • GeekyDanish
    GeekyDanish8 个月 前

    ''' Heap -> createHeap() top() push() pop() ''' # creating heap def createHeap(): heap = [] return heap # return the top element def top(heap): if len(heap) == 0: return -1 else: return heap[len(heap)-1] # Min.heap # push def push(heap,x): if len(heap) == 0: heap.append(x) elif len(heap) > 0 and x heap.append(x) elif len(heap) > 0 and x > top(heap): heap.insert(0,x) # pop def pop(heap): if len(heap) == 0: return -1 else: heap.pop() # prob logic def sort_k_sorted(arr,n,k): sort_list = [] h = createHeap() for i in range(0,n): push(h,arr[i]) if len(h) > k: sort_list.append(h.pop()) return sort_list + sorted(h) if __name__ =="__main__": arr = [3,2,1,5,6,4] n = len(arr) k = 2 print(sort_k_sorted(arr,n,k))

  • Akarsh Jaiswal
    Akarsh Jaiswal8 个月 前


  • Saurabh Sen
    Saurabh Sen8 个月 前

    Your explanations are awsome. I got stuck in this question "Smallest range in K lists" can you please make a video on this.

  • babbar utkarsh
    babbar utkarsh9 个月 前

    It’s May ,waiting for backtracking, greedy, graphs, trees patiently. 😊😊

  • ROHIT gaming

    ROHIT gaming

    10 天 前


  • ROHIT gaming

    ROHIT gaming

    10 天 前

    @Dhruvil Bhuptani usne kuch ni padaya dsa drame marta hai bs

  • Dhruvil Bhuptani

    Dhruvil Bhuptani

    个月 前

    babbar love babbar ka video dekho jake beta.

  • Vikrant Prasad

    Vikrant Prasad

    7 个月 前

    @ravi ashwin I think due to lockdown he is not able to make any new videos

  • ravi ashwin

    ravi ashwin

    8 个月 前

    @markos webinar on backtracking by coding ninjas and graph by coding blocks is available in youtube

  • babbar utkarsh
    babbar utkarsh9 个月 前


  • louer le seigneur
    louer le seigneur9 个月 前


  • Aditya Verma

    Aditya Verma

    9 个月 前


  • Pruthvi Raj K
    Pruthvi Raj K9 个月 前

    //ide.geeksforgeeks.org/CfUURWtG7j //Ascending Order Min-heap...descending Order Max Heap.....🤘

  • pulkit jain
    pulkit jain9 个月 前

    Practice problem link : practice.geeksforgeeks.org/problems/nearly-sorted-algorithm/0

  • Ankoor Bhagat
    Ankoor Bhagat9 个月 前

    #include #include #include using namespace std; int main() { vector A = {6, 5, 3, 2, 8, 10, 9}; int n = A.size(); priority_queue minHeap; int k = 3; // Push k elements in min heap for (int i=0; i

  • Ankoor Bhagat

    Ankoor Bhagat

    个月 前

    @24K_ Gold std::priority_queue class implements a minheap by default. This problem needs maxheap so I am pushing negative of integers... 10 in the example is largest so I want it to be on top so I push -10 since -10 is smallest it will be on top...later I just apply negative in front to get correct number...

  • 24K_ Gold

    24K_ Gold

    个月 前

    bro what is the logic behind -minHeap.top(), i mean what is the significance of minus here! waiting for your kind rply'

  • Sai Charan
    Sai Charan10 个月 前

    bhai how did you identify that we should use min heap?

  • Dayamoy Adhikari

    Dayamoy Adhikari

    9 个月 前

    @Jagrit Bhupal Agreed! I think one must identify the type of heap based on what is required.. Since we require the ascending order of elements, take the min-heap. It's unlike Kth largest/smallest where type of heap used is opposite to the requirement because we're eliminating the smallest/largest element i.e. it's a different thought process than this question.

  • Jagrit Bhupal

    Jagrit Bhupal

    9 个月 前

    Here, we need to print array in ascending order so smallest element in k range will come first, that is top of min heap. If we need to print array in descending order, I think we will use max-heap.

  • Aditya Verma

    Aditya Verma

    9 个月 前

    Brother, I have covered that already in the starting videos of the series, please refer them