Re: [algogeeks] Find the Max from each sub-array of size k
can find one more solution in my blog http://pandey123.wordpress.com/ check it... and tell me if you have any doubt... On Sat, Jun 23, 2012 at 11:52 PM, Akshat Sapra sapraaks...@gmail.comwrote: To do this question in O(n) time follow the post Segment trees in this post of topcoder http://community.topcoder.com/tc?module=Staticd1=tutorialsd2=lowestCommonAncestor Here in this given algorithm preprocessing time in O(n) and query time is O(log n). -- Akshat Sapra Under Graduation(B.Tech) IIIT-Allahabad(Amethi Campus) *--* sapraaks...@gmail.com akshatsapr...@gmail.com rit20009008@ rit20009...@gmail.comiiita.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the Max from each sub-array of size k
To do this question in O(n) time follow the post Segment trees in this post of topcoder http://community.topcoder.com/tc?module=Staticd1=tutorialsd2=lowestCommonAncestor Here in this given algorithm preprocessing time in O(n) and query time is O(log n). -- Akshat Sapra Under Graduation(B.Tech) IIIT-Allahabad(Amethi Campus) *--* sapraaks...@gmail.com akshatsapr...@gmail.com rit20009008@ rit20009...@gmail.comiiita.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the Max from each sub-array of size k
We can also build a Balanced BST for the window elements and on each shift we need to have a delete operation and add oeration. O(n logk) Also we can add the Shashank algo where we check if the newly added element is greater than the current BST's max element. So we can discard the current BSt and start a new BST Thanks Ramindar Singh On Friday, 2 September 2011 09:04:26 UTC+5:30, Anup wrote: Given an unsorted Array A and any integer k where k = size of A Print the maximum of each sub-array of size k of A. eg: A = [ 3, 5, 1, 9, 0, 4, -1, 7 ] k = 4 Max: 9 9 9 9 7 -- Anup Ghatage -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/A1g3pH1GCgUJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the Max from each sub-array of size k
Your algo is good but i don get the part where A[i] (current element) is less than the first element? Do we enqueue it? And if yes, when the front element is popped out , how is the next max found in front of the queue? If you could give an example with the growing queue. On Friday, 2 September 2011 15:43:41 UTC+5:30, WgpShashank wrote: Hi Anup , here is naive approach There is a sliding window of size w which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example: The array is [1 3 -1 -3 5 3 6 7], and w is 3. Window position Max --- - [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 The obvious solution with run time complexity of O(nw) is which is not efficient enough. Every time the window is moved, we have to search for the maximum from w elements in the window. where w is size of window n is size of array 1st Method(Naive Approach) Data Structure Used : Array Algorithm: A.for all i=0 to n-w+1 (we should have at-least w elements in window) B.for all j=i to i+w (keep incrementing windows size form left to right) C find maximum inn each window print it or put in array (Auxiliary) For more efficient approaches you can have a look here http://shashank7s.blogspot.com/2011/06/given-array-and-integer-k-find-maximum.html correct me if anything wrong or other approaches you can thing of ? Thanks Shashank Mani Computer Science Birla Institute of Technology Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/giQA3tSNZtAJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the Max from each sub-array of size k
@ALL can be solved using segment tree . :-) On Fri, Sep 2, 2011 at 9:49 AM, Anup Ghatage ghat...@gmail.com wrote: I just checked Shashank's blog post. The Deque solution is awesome :) -- Anup Ghatage -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the Max from each sub-array of size k
Hi Anup , here is naive approach There is a sliding window of size w which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example: The array is [1 3 -1 -3 5 3 6 7], and w is 3. Window position Max --- - [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 The obvious solution with run time complexity of O(nw) is which is not efficient enough. Every time the window is moved, we have to search for the maximum from w elements in the window. where w is size of window n is size of array 1st Method(Naive Approach) Data Structure Used : Array Algorithm: A.for all i=0 to n-w+1 (we should have at-least w elements in window) B.for all j=i to i+w (keep incrementing windows size form left to right) C find maximum inn each window print it or put in array (Auxiliary) For more efficient approaches you can have a look here http://shashank7s.blogspot.com/2011/06/given-array-and-integer-k-find-maximum.html correct me if anything wrong or other approaches you can thing of ? Thanks Shashank Mani Computer Science Birla Institute of Technology Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/m1R83UHfc2UJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the Max from each sub-array of size k
I made a small program with window size k = 2;
int max(int n, int m)
{
if ( n m )
return n;
else
return m;
}
int main()
{
int arr[8]={3,5,1,9,0,4,-1,7};
int i,j;
for (i=0;i!=j i=7;i++)
for (j=0;j!=i j=7; j++)
{
int k = max(arr[i], arr[j]);
cout[arr[i],arr[j]] = ;
coutk\n;
}
return 0;
}
output is :
[5,3] = 5
[1,3] = 3
[1,5] = 5
[9,3] = 9
[9,5] = 9
[9,1] = 9
[0,3] = 3
[0,5] = 5
[0,1] = 1
[0,9] = 9
[4,3] = 4
[4,5] = 5
[4,1] = 4
[4,9] = 9
[4,0] = 4
[-1,3] = 3
[-1,5] = 5
[-1,1] = 1
[-1,9] = 9
[-1,0] = 0
[-1,4] = 4
[7,3] = 7
[7,5] = 7
[7,1] = 7
[7,9] = 9
[7,0] = 7
[7,4] = 7
[7,-1] = 7
On Fri, Sep 2, 2011 at 3:43 PM, WgpShashank shashank7andr...@gmail.comwrote:
Hi Anup , here is naive approach
There is a sliding window of size w which is moving from the very left of
the array to the very right. You can only see the w numbers in the window.
Each time the sliding window moves rightwards by one position.
Following is an example:
The array is [1 3 -1 -3 5 3 6 7], and w is 3.
Window position Max
--- -
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
The obvious solution with run time complexity of O(nw) is which is not
efficient enough. Every time the window is moved, we have to search for the
maximum from w elements in the window. where w is size of window n is size
of array
1st Method(Naive Approach)
Data Structure Used : Array
Algorithm: A.for all i=0 to n-w+1 (we should have at-least w elements in
window)
B.for all j=i to i+w (keep incrementing windows size form left to right)
C find maximum inn each window print it or put in array (Auxiliary)
For more efficient approaches you can have a look here
http://shashank7s.blogspot.com/2011/06/given-array-and-integer-k-find-maximum.html
correct me if anything wrong or other approaches you can thing of ?
Thanks
Shashank Mani
Computer Science
Birla Institute of Technology Mesra
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/m1R83UHfc2UJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the Max from each sub-array of size k
I think Dave has already given a good solution in earlier post. first make a max heap of first k elements and then print max value which is root . now add next element in heap and again print max value follow this procedure till you reach end of an array. On Fri, Sep 2, 2011 at 9:04 AM, Anup Ghatage ghat...@gmail.com wrote: Given an unsorted Array A and any integer k where k = size of A Print the maximum of each sub-array of size k of A. eg: A = [ 3, 5, 1, 9, 0, 4, -1, 7 ] k = 4 Max: 9 9 9 9 7 -- Anup Ghatage -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the Max from each sub-array of size k
i think the problem can also be solved by DP.. arr is the original array.. final is the array required.. for(i=0;in;i++) final[i]=arr[i]; for(i=2;i=k;i++) for(j=0;jn-i+2;j++) final[i]=max( final[j] , final[j+1]); initial n-i+2 entries in the array final contains the answer.. time complexity (O(nk))... correct me if i'm wrong anywhere... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/XWcOWYyt8B0J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the Max from each sub-array of size k
I just checked Shashank's blog post. The Deque solution is awesome :) -- Anup Ghatage -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Find the Max from each sub-array of size k Options
comparison/benchmarks of the 1) naive method, which just calls max with every new index, up to size of array - k 2) my method , which only makes a call to max if the old max is out of range or the newest/very rightmost element is greater than max ruby code: [image: max_subarray_text.png] benchmark output: [image: max_subarray_output.png] To test this, I had shuffled an array of size 1000 with k=25.I also called each method 1000 times, which shows 5x improvement over naive method icy` -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. max_subarray_output.pngmax_subarray_text.png
[algogeeks] Find the Max from each sub-array of size k
Given an unsorted Array A and any integer k where k = size of A Print the maximum of each sub-array of size k of A. eg: A = [ 3, 5, 1, 9, 0, 4, -1, 7 ] k = 4 Max: 9 9 9 9 7 -- Anup Ghatage -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the Max from each sub-array of size k
how did u get such o/p for k=4 ?? i dint get plz expalin On Fri, Sep 2, 2011 at 9:04 AM, Anup Ghatage ghat...@gmail.com wrote: Given an unsorted Array A and any integer k where k = size of A Print the maximum of each sub-array of size k of A. eg: A = [ 3, 5, 1, 9, 0, 4, -1, 7 ] k = 4 Max: 9 9 9 9 7 -- Anup Ghatage -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
