is this always return full sorted array or if we take arr[] = {6,5,3,4,2,8,9} then the output will be {3,2,4,5,6,8,9} is it correct ans?? im confuse lit bit
can you please explain why you used minh.top() to insert element in the array. whereas we can you use minh.top() directly as it returns that element also and even reduces one step.
Code for java ``` class Solution { //Function to return the sorted array. ArrayList nearlySorted(int arr[], int num, int k) { // your code here ArrayList list = new ArrayList(); PriorityQueue q = new PriorityQueue(); for(int i = 0 ;ik){ list.add(q.poll()); } } while(!q.isEmpty()){ list.add(q.poll()); } return list; } } ``` Thanks for the explaination sir
Anyone or Aditya Verma If you are saying that min element is always at the top and the remaining elements in heap are not necessarliy sorted then why did you inserted 9 (8:36) at a sorted position rather than at the lowest. you have taken all the examples where heap elements are sorted below top.
But if we have 4 in place of 8. do the algorithm still work? cause then the order after this algorithm would be 2,3,4,5,6 but 6 can't move more than 3 places from it's original position.
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 .....
JAVA CODE : public static ArrayList nearlySorted(int arr[], int k) { ArrayList l = new ArrayList(); PriorityQueue q = new PriorityQueue(); for (int i = 0; i < arr.length; i++) { q.add(arr[i]); if (q.size() > k) { l.add(q.remove()); } } while (!q.isEmpty()) { l.add(q.remove()); } return l; }
Hi, why we use a heap size k+1, i havent get the intuition behind this. Can we use a heap of other size?. Why we are making the heap of size k+1 for they stating upto k+1 elements is sorted. Please clarify!🤒
Let's take example of 0th index : The element which has its position at 0th index may be present atmost k distance away from 0th index. So we store the 0th element and the next k elements to find the smallest among them, so that we can put it at the 0th index. Hope it helped you.
well actually there we were finding k th smallest element whereas here we are finding smallest element.here we require the top element to be smallest hence min heap,whereas to find kth smallest element we need the smallest element at the bottom,then 2nd smallest and so on.. till kth smallest
@@rohitjadhav512 Hi Rohit, when we dry run it ,the first element that goes outside the heap would be 7 and then 4 would be inserted and pop up in next iteration. So how is this test case passing. Please feel free if I am wrong and explain
@@sakshamsrivastava6280 no bro...7 won't pop first...4 will get pop first because IF(heap.size() > k) satisfies when heap.size() become 5 and at that time heap top would be 4 n that 4 will get pop....
The code in Java: class Solution { //Function to return the sorted array. ArrayList nearlySorted(int arr[], int n, int k) { // your code here PriorityQueue minHeap = new PriorityQueue();
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.
@@jagrit07 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.
Here is my Python solution guys who are coding in python may be it will help : from heapq import heappop, heappush,heapify arr =[6, 5, 3, 2, 8, 10, 9] k = 3 min_heap = [] sorted_lis = [] for i in range(len(arr)): heappush(min_heap,arr[i]) if len(min_heap)>k: res =heappop(min_heap) sorted_lis.append(res) while min_heap!=[]: sorted_lis.append(heappop(min_heap)) print(sorted_lis)
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
Bhai Why you used priority queue I know they are heap but we are not creating heap it's the priority queue which is queue in itself agr array s min heap bna hota to maza ajata aur
mycodeschool channel dekh lo. usme... Selection, Bubble, Insertion, Merge, Quicksort tak ache se hai... uske bad Jenny's Lecture mein.. Heap Sort ache se diya hua hai itne tak Comparision based sorting algo's hai.. jo books mein hoti hai.. max woh O (n logn) ka performance dega. Phir non-comparision based sorting algorithms aa jaega... Counting, Radix, Bucket etc etc.
#python implementation import heapq li=[6,5,3,2,8,10,9] heap=[] k=3 v=[] for i in range(len(li)): heapq.heappush(heap,li[i]) if len(heap)>k: v.append(heap[0]) heapq.heappop(heap) while len(heap)>0: v.append(heap[0]) heapq.heappop(heap) print(v)
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.
@@yari4686 std::sort uses intro sort which analyze the size of vector and depending on that apply sorting technique either insertion sort or merge sort on number of elements
I think this implementation will also work priority_queue minh; int j=0; for(int i=0;ik){ a[i-k]=minh.top(); minh.pop(); j++; } } while(minh.size()!=0){ a[j]=minh.top(); minh.pop(); j++;
I believe this should be Java soultion let me know if anything can be corrected, Thanks static int[] sort(int[] arr, int k) { PriorityQueue minH = new PriorityQueue((a,b) -> a - b); int[] arr1 = new int[arr.length]; int j=0; for(int i = 0;ik) { arr1[j]=minH.poll(); j++; } } while(minH.size()>0) { arr1[j]=minH.poll(); j++; } return arr1; }
Java Code: class Solution{ ArrayList nearlySorted(int arr[], int n, int k){ ArrayList list = new ArrayList(); PriorityQueue minH = new PriorityQueue(); for(int i=0; i
0:00 *Introduction*
1:00 *Problem Statement*
3:00 *Sorting Idea*
4:00 *Heap approach & Explanation*
10:00 *Code Implementation*
*Nicely Explained : )*
0:00 flexing with a pen
Bruh , No one even made me understand the problem this good let alone make me undersatand solution, you are gifted.
Crisp and Precise, Man U just nailed it though ! 🤛🏻
Your explanations are awsome. I got stuck in this question "Smallest range in K lists" can you please make a video on this.
Bhaiya jis tarah ap samjhate ho , 1 number
This was asked to me in PhonePe interview (Cali, US ) position
Really helpfull.Finally understand the use of k sorted array to sort using heap,Thank you once again.
// Nearly sorted GFG
vector nearlySorted(int arr[], int n, int k){
priority_queueminh;
vectorans;
for(int i=0;ik)
{
ans.push_back(minh.top());
minh.pop();
}
}
while(minh.size()>0)
{
ans.push_back(minh.top());
minh.pop();
}
return ans;
No body could have explained ot better 😌🤘💯🔥
It’s May ,waiting for backtracking, greedy, graphs, trees patiently. 😊😊
yes..patiently
@@nagarjuna119 yes i'm also waiting for backtracking and graph.. there is no any good sources available on these topics .
@@markos8955 webinar on backtracking by coding ninjas and graph by coding blocks is available in youtube
@@raviashwin1157 I think due to lockdown he is not able to make any new videos
babbar love babbar ka video dekho jake beta.
The original code :
---------------------------------------
#include
#include
#include
using namespace std;
void sort_k_sorted_array(int *arr, int n, int k)
{
priority_queue minh;
int j=0;
for(int i=0; ik)
{
arr[j]=minh.top();
minh.pop();
j++;
}
}
while(minh.size()>0)
{
j++;
arr[j]=minh.top();
minh.pop();
}
}
void print_array(int *arr, int n)
{
for(int i=0; i
is this always return full sorted array or if we take arr[] = {6,5,3,4,2,8,9} then the output will be {3,2,4,5,6,8,9} is it correct ans?? im confuse lit bit
@@mitashiv3918 the element should be from [i-k,i+k] if u take k=3 element 2's index in matrix should be 3 or less
can you please explain why you used minh.top() to insert element in the array. whereas we can you use minh.top() directly as it returns that element also and even reduces one step.
Sir your videos are awesome, hats off to you .... Plzzz backtracking upload kardo
Code for java
```
class Solution
{
//Function to return the sorted array.
ArrayList nearlySorted(int arr[], int num, int k)
{
// your code here
ArrayList list = new ArrayList();
PriorityQueue q = new PriorityQueue();
for(int i = 0 ;ik){
list.add(q.poll());
}
}
while(!q.isEmpty()){
list.add(q.poll());
}
return list;
}
}
```
Thanks for the explaination sir
Thankyou bro
Ek video pen ghumane ki bhi bana do bhaiya, bohot cool lgta hai 😍😍😂😂
bruh the pen is not rotating just watch it by slowing the video..
Thank You So Much for this wonderful video....🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Awesome explanation bhiya 😄😄 Just keep up the good work!!
Thank you so much bro for this valuable content.so happy to learn
It was very helpful...Thanks bhaiya
Great explanation!
Anyone or Aditya Verma
If you are saying that min element is always at the top and the remaining elements in heap are not necessarliy sorted then why did you inserted 9 (8:36) at a sorted position rather than at the lowest. you have taken all the examples where heap elements are sorted below top.
Aditya is correct . basically in minHeap , after popping min element re hepify runs which brings only min element to top. Check re hepify once
@@JameS00989 hello bhai kon se college se ho..
Great stuff Aditya!!
Great explaination by u😊😊
Excellent explanation Sir.
But if we have 4 in place of 8. do the algorithm still work? cause then the order after this algorithm would be 2,3,4,5,6 but 6 can't move more than 3 places from it's original position.
Mai ye padh kr gya tha, Heap ka implementation puchh liya.
great video bhai!!
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 .....
Yes STL is allowed
JAVA CODE :
public static ArrayList nearlySorted(int arr[], int k) {
ArrayList l = new ArrayList();
PriorityQueue q = new PriorityQueue();
for (int i = 0; i < arr.length; i++) {
q.add(arr[i]);
if (q.size() > k) {
l.add(q.remove());
}
}
while (!q.isEmpty()) {
l.add(q.remove());
}
return l;
}
We could update the given array itself as the k elements were added into the heap at any point of time.
Sir plz you should also put link of question in description. Nice exp
Please upload more you are amazing
u are a legend 😍😍😍😍😍😍
Hi, why we use a heap size k+1, i havent get the intuition behind this. Can we use a heap of other size?. Why we are making the heap of size k+1 for they stating upto k+1 elements is sorted. Please clarify!🤒
Let's take example of 0th index :
The element which has its position at 0th index may be present atmost k distance away from 0th index.
So we store the 0th element and the next k elements to find the smallest among them, so that we can put it at the 0th index.
Hope it helped you.
Why are we using min heap here when we can interpret the question as finding smallest element in k terms. Aren't we supposed to use max heap then
well actually there we were finding k th smallest element whereas here we are finding smallest element.here we require the top element to be smallest hence min heap,whereas to find kth smallest element we need the smallest element at the bottom,then 2nd smallest and so on.. till kth smallest
Thank you very much.
what should be the size of the heap?if it is k+1 then why?
Nice explaination !!
Video Stands Out even in 2024
arr[] = {10, 9, 8, 7, 4, 70, 60, 50}
k = 4, i think this case would fail for this algorithm.
Please correct me if I am wrong.
it works
@@rohitjadhav512 Hi Rohit, when we dry run it ,the first element that goes outside the heap would be 7 and then 4 would be inserted and pop up in next iteration.
So how is this test case passing.
Please feel free if I am wrong and explain
@@sakshamsrivastava6280 no bro...7 won't pop first...4 will get pop first because IF(heap.size() > k) satisfies when heap.size() become 5 and at that time heap top would be 4 n that 4 will get pop....
Yes it failing for k=3
The code in Java:
class Solution
{
//Function to return the sorted array.
ArrayList nearlySorted(int arr[], int n, int k)
{
// your code here
PriorityQueue minHeap = new PriorityQueue();
ArrayList ans = new ArrayList();
for(int i=0;ik){
ans.add(minHeap.peek());
minHeap.poll();
}
}
for(int i=0;i
int j=0 Arr[j++] inspace instead of list
What is functionality of priority queue in JS. Like we have used directly STL for C++. What I can use in JS.
Same problem in GFG is named as "Nearly sorted"
It's June 2023, still waiting for graph playlist 🙃
If k is 2 then the first value will be 3 instead of 2. Kindly cover this case!!!
I think if K is changed, so will the Input array. The input array in this question is designed for k=3.
at 3:05 I paused for a while and boom I wrote the whole solution by myself. Thanks brother but thodi cheating hai yeh. I'll improve on this
0:00 intro
1:00 ps
bhai how did you identify that we should use min heap?
Brother, I have covered that already in the starting videos of the series, please refer them
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.
@@jagrit07 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.
@@damercy I think Sai Charan's comment should be pinned and yours (& Jagrit Bhupal too) answer should be hearted!
@@jagrit07 Wow this was very helpful. Thank you!
hey , bro how do you swirl your pen , during tutorial =????????
sir aap kahan tthe aaj tak. Thanks a lot.
Perfect🤩
how i know that minheap will be used in this question,kindly reply......
Thank you 💕
what if its is asked to modify in the same array
what if in the place of index 5 (which is 8) is 1?
what would the min heap do?
i cant not go that far only have k far from it's right position
Thank you 😊
Awesome bro
Here is my Python solution guys who are coding in python may be it will help :
from heapq import heappop, heappush,heapify
arr =[6, 5, 3, 2, 8, 10, 9]
k = 3
min_heap = []
sorted_lis = []
for i in range(len(arr)):
heappush(min_heap,arr[i])
if len(min_heap)>k:
res =heappop(min_heap)
sorted_lis.append(res)
while min_heap!=[]:
sorted_lis.append(heappop(min_heap))
print(sorted_lis)
Brother how can we implement max heap using heapq in python?
Excellent Explanation!!!!
totally out of context question
Bro are you from UP??
Bareily sa hain
MP, most probably. UP people don't say "Hum" as "Uppan".
@@AdityaRaj222 EXACTLY bro
Heap like magic😂😂
for arr[]:{5,6,4,7,2,3}; and k = 2. How we can say that at index 0 the element to be present has to be k distance away?
In the requirement of the question it is mentioned that the provided array will be k-sorted (not fully un-sorted or sorted).
@@SuperNirajpandey okay, I got it, Thanks!
Is there any leetcode problem similar to this ?
thank you bhai
Ok rather than taking in vector make are pointer and change whole arr
one doubt why dont we use max heap ie any particular reason for choosing min heap over max heap??? plz answer
see some previous comments, it's explained.
Aditya always green flag 👏
is it merge k sorted arrays?
Why heap?
Bro i-k to i+k ,,,,,,so stack size should be 2k na????????????????????????
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
@@shreshthsingh7744 bro can u help me with the code
Teetar ke do aage teetar, teetar ke do peeche teetar, bolo kitne teetar?
--- Teen, not paanch
Similarly, heap size should be k, not 2k.
sum up 9:40
Ap compatative programming ki bhi video bana do
bhai eak tutorial pen ghumane pe bhi bana do plis
Thank you :)
can you still do this if k is unknown?
no
@@rohitjadhav512 what do u do then?
@@atharvsakhala9469 normal sorting use kro na fir
Bhai Why you used priority queue I know they are heap but we are not creating heap it's the priority queue which is queue in itself agr array s min heap bna hota to maza ajata aur
sab question inke flipkart ke interview me aaye huye hai 😂😂
sir mauj krdi aapne to
bas ho sake to bit pe videos or bana do
or sir pen ghumana b sikha do
bhai merge sort ka code likhneme dikkat jaati hai ...plss uspe ek video banao
mycodeschool channel dekh lo.
usme... Selection, Bubble, Insertion, Merge, Quicksort tak ache se hai...
uske bad Jenny's Lecture mein.. Heap Sort ache se diya hua hai
itne tak Comparision based sorting algo's hai.. jo books mein hoti hai.. max woh O (n logn) ka performance dega.
Phir non-comparision based sorting algorithms aa jaega...
Counting, Radix, Bucket etc etc.
#python implementation
import heapq
li=[6,5,3,2,8,10,9]
heap=[]
k=3
v=[]
for i in range(len(li)):
heapq.heappush(heap,li[i])
if len(heap)>k:
v.append(heap[0])
heapq.heappop(heap)
while len(heap)>0:
v.append(heap[0])
heapq.heappop(heap)
print(v)
What is time complexity of this
my reheapifyis not working
GFG Answer:
#include
using namespace std;
int main() {
vector v;
priority_queue minh;
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
int arr[n];
for(int i=0;i>arr[i];
v.clear();
for(int i=0;ik){
v.push_back(minh.top());
minh.pop();
}
}
while(minh.size()>0)
{
v.push_back(minh.top());
minh.pop();
}
for(int i=0;i
Can we do this questions in O(1) space complexity??
yup,with insertion sort with timr complexity O(n*k)
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.
what is the complexity of inbuilt sort for a vector??
inbuilt sort means ? std::sort() ?
std::sort() is quick sort, infact most library sorting algorithms are quick sort, which is O(n logn)
@@PabitraPadhy it actually depends on number of elements in vector either quick sort Or merge sort
O(nlog(n))
@@yashodeepdhas8408 How it's depends on vector elements can u explain...?
@@yari4686 std::sort uses intro sort which analyze the size of vector and depending on that apply sorting technique either insertion sort or merge sort on number of elements
youtube should have a 3x button😅
You could do that by editing the javascript of the page.
GFG VIDEO CODE :
class Solution
{
public:
//Function to return the sorted array.
vector nearlySorted(int arr[], int num, int K){
priority_queue minh;
vector v;
for(int i=0;iK)
{
v.push_back(minh.top());
minh.pop();
}
}
while(minh.size()>0)
{
v.push_back(minh.top());
minh.pop();
}
return v;
}
};
merci
bienvenu
bro code ka video hai?
great
I think this implementation will also work
priority_queue minh;
int j=0;
for(int i=0;ik){
a[i-k]=minh.top();
minh.pop();
j++;
}
}
while(minh.size()!=0){
a[j]=minh.top();
minh.pop();
j++;
}
Bro if you could do the videos in English, it would be really great.
Sir plz start graphs😔😭
Bro i watched all heap videos and i think you have skipped heapify in its entirety, pls make vid abt it
You can watch heap playlist by TECH DOSE. Aditya bhaiya had mentioned it in the first video that he would focus on heap stl
Sir, please tell how to implement heap in java.
For MinHeap use PriorityQueueminH = new PriorityQueue(); For MaxHeap use PriorityQueuemaxH = new PriorityQueue(Collections.reverseOrder());
@@DINESHKUMAR-gw1kz why you pass Collections.reverseOrder() inside the constructor of priorityQueue ?
3:49
can you exaplin why it is n log k please?
Because we are comparing (sorting) only k elements at a time
Bro sde 2 bn gye
I believe this should be Java soultion let me know if anything can be corrected, Thanks
static int[] sort(int[] arr, int k) {
PriorityQueue minH = new PriorityQueue((a,b) -> a - b);
int[] arr1 = new int[arr.length];
int j=0;
for(int i = 0;ik) {
arr1[j]=minH.poll();
j++;
}
}
while(minH.size()>0) {
arr1[j]=minH.poll();
j++;
}
return arr1;
}
woh sab hatao pehle pen ghumane ki alag se video tutorial banao , mai tabse try kr rha hu
Java GFG Ans:-
class Solution
{
ArrayList nearlySorted(int arr[], int num, int k)
{
PriorityQueue minHeap = new PriorityQueue();
ArrayList al = new ArrayList();
for(int a: arr){
minHeap.add(a);
if(minHeap.size() > k){
al.add(minHeap.poll());
}
}
while(minHeap.size() != 0){
al.add(minHeap.poll());
}
return al;
}
}
can u send the question link..?
Java Code:
class Solution{
ArrayList nearlySorted(int arr[], int n, int k){
ArrayList list = new ArrayList();
PriorityQueue minH = new PriorityQueue();
for(int i=0; i