Re: [algogeeks] Constant time solution needed
@vicky your approach doesn't work for (x1,y1) = (1,2) (x2,y2) = (2,3) By your Approach:- Ans= sumArray[x2][y2] - sumArray[x1][y1] + ip[x1][y1]=66-18+6= *54* But Actual Ans is 6+7+10+11=*34* On Sun, Aug 12, 2012 at 8:19 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: Lets build the array for the example you gave. i/p: 0 1 2 3 4 5 6 7 8 9 10 11 (x1,y1) = (0,0) (x2,y2) = (1,2) sumArray 0 1 23 4 10 18 28 12 27 45 66 (will take O(n^2) to build above array) So now when you get coordinates as input, you can calc the sum by Ans = sumArray[x2][y2] - sumArray[x1][y1] + ip[x1][y1] For our case it will be Ans = 18-0+0 = 18 Please lemme know if any bugs with the logic. On Sun, Aug 12, 2012 at 6:27 PM, Srividhya Sampath srisam261...@gmail.com wrote: @ Vicky Can yo explain with an illustration ? On Sat, Aug 11, 2012 at 10:07 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: May be you can consider creating a 2d array to pre process and store all the rectangle sums as a dependent subproblem, the sum of larger rect will be currValuesAdded+OldRectSum. So when you get the coordinate as input u can calc the needed sum by subtracting sum of big rect and small rect which is not included in the given coordinates. This can be called constant time if u don't include the preprocessing time. On Sat, Aug 11, 2012 at 9:57 PM, adarsh kumar algog...@gmail.comwrote: Sum of the integers meaning? Do you mind giving an example test case? regards. On Sat, Aug 11, 2012 at 7:10 PM, Srividhya srisam261...@gmail.comwrote: hi all:) The coordinates of a rectangle will be specified. there is a matrix of integers. yo should find the sum of the integers that fall in the region specified by the coordinates . The solution to be in constant time . -- 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/-/qHSmXBshmS4J. 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. -- Cheers, Vicky -- 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. -- Cheers, Vicky -- 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. -- -- ‘Kailash Bagaria’ B-tech 4th year Computer Science Engineering Indian Institute of Technology, Roorkee Roorkee, India (247667) -- 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] Constant time solution needed
Hey I just gave an idea, I believe solve it yourself :) I appreciate your effort. On Tue, Aug 14, 2012 at 4:34 PM, Kailash Bagaria kbkailashbaga...@gmail.com wrote: @vicky your approach doesn't work for (x1,y1) = (1,2) (x2,y2) = (2,3) By your Approach:- Ans= sumArray[x2][y2] - sumArray[x1][y1] + ip[x1][y1]=66-18+6=*54* But Actual Ans is 6+7+10+11=*34* On Sun, Aug 12, 2012 at 8:19 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: Lets build the array for the example you gave. i/p: 0 1 2 3 4 5 6 7 8 9 10 11 (x1,y1) = (0,0) (x2,y2) = (1,2) sumArray 0 1 23 4 10 18 28 12 27 45 66 (will take O(n^2) to build above array) So now when you get coordinates as input, you can calc the sum by Ans = sumArray[x2][y2] - sumArray[x1][y1] + ip[x1][y1] For our case it will be Ans = 18-0+0 = 18 Please lemme know if any bugs with the logic. On Sun, Aug 12, 2012 at 6:27 PM, Srividhya Sampath srisam261...@gmail.com wrote: @ Vicky Can yo explain with an illustration ? On Sat, Aug 11, 2012 at 10:07 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: May be you can consider creating a 2d array to pre process and store all the rectangle sums as a dependent subproblem, the sum of larger rect will be currValuesAdded+OldRectSum. So when you get the coordinate as input u can calc the needed sum by subtracting sum of big rect and small rect which is not included in the given coordinates. This can be called constant time if u don't include the preprocessing time. On Sat, Aug 11, 2012 at 9:57 PM, adarsh kumar algog...@gmail.comwrote: Sum of the integers meaning? Do you mind giving an example test case? regards. On Sat, Aug 11, 2012 at 7:10 PM, Srividhya srisam261...@gmail.comwrote: hi all:) The coordinates of a rectangle will be specified. there is a matrix of integers. yo should find the sum of the integers that fall in the region specified by the coordinates . The solution to be in constant time . -- 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/-/qHSmXBshmS4J. 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. -- Cheers, Vicky -- 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. -- Cheers, Vicky -- 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. -- -- ‘Kailash Bagaria’ B-tech 4th year Computer Science Engineering Indian Institute of Technology, Roorkee Roorkee, India (247667) -- 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. -- Cheers, Vicky -- 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] Constant time solution needed
@vicky Got it . thanks ..is it possible to ignore the preprocessing time when calculating time complexity? On Sun, Aug 12, 2012 at 10:02 PM, shady sinv...@gmail.com wrote: @venkat +1 On Sun, Aug 12, 2012 at 9:09 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: @Arun: This approach is constant time once the array is build for any queries that follows. :) You know sum for all possible rectangles in the given 2d array thats makes it better than computing sum for each input. Hope it makes sense On Sun, Aug 12, 2012 at 9:07 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: Fine, the basic idea of using dp here is sum of each rectangle is a dependent sub problem. So when u find sum for smaller rectangle we can use it to compute sum of bigger rectangle with new coordinates added to previous small rectangle. So u can compute the sum array by using this formula sum[i][j] = sum[i-1][j-1] + (sum[i-1][j] - sum[i-1][j-1]) + (sum[i][j-1] - sum[i-1][j-1])+ip[i][j] [smaller rect] [that row sum value][that col sum value] On Sun, Aug 12, 2012 at 8:54 PM, Srividhya Sampath srisam261...@gmail.com wrote: @vicky can yo explain the logic behind the 'Sum Array' computation (if possible elaborately )? On Sun, Aug 12, 2012 at 8:19 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: Lets build the array for the example you gave. i/p: 0 1 2 3 4 5 6 7 8 9 10 11 (x1,y1) = (0,0) (x2,y2) = (1,2) sumArray 0 1 23 4 10 18 28 12 27 45 66 (will take O(n^2) to build above array) So now when you get coordinates as input, you can calc the sum by Ans = sumArray[x2][y2] - sumArray[x1][y1] + ip[x1][y1] For our case it will be Ans = 18-0+0 = 18 Please lemme know if any bugs with the logic. On Sun, Aug 12, 2012 at 6:27 PM, Srividhya Sampath srisam261...@gmail.com wrote: @ Vicky Can yo explain with an illustration ? On Sat, Aug 11, 2012 at 10:07 PM, ~*~VICKY~*~ venkat.jun...@gmail.com wrote: May be you can consider creating a 2d array to pre process and store all the rectangle sums as a dependent subproblem, the sum of larger rect will be currValuesAdded+OldRectSum. So when you get the coordinate as input u can calc the needed sum by subtracting sum of big rect and small rect which is not included in the given coordinates. This can be called constant time if u don't include the preprocessing time. On Sat, Aug 11, 2012 at 9:57 PM, adarsh kumar algog...@gmail.comwrote: Sum of the integers meaning? Do you mind giving an example test case? regards. On Sat, Aug 11, 2012 at 7:10 PM, Srividhya srisam261...@gmail.comwrote: hi all:) The coordinates of a rectangle will be specified. there is a matrix of integers. yo should find the sum of the integers that fall in the region specified by the coordinates . The solution to be in constant time . -- 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/-/qHSmXBshmS4J. 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. -- Cheers, Vicky -- 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. -- Cheers, Vicky -- 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
Re: [algogeeks] Constant time solution needed
Its something which is good to have discussion with the interviewer rather than making any assumption. :) On Mon, Aug 13, 2012 at 6:07 PM, Srividhya Sampath srisam261...@gmail.comwrote: @vicky Got it . thanks ..is it possible to ignore the preprocessing time when calculating time complexity? On Sun, Aug 12, 2012 at 10:02 PM, shady sinv...@gmail.com wrote: @venkat +1 On Sun, Aug 12, 2012 at 9:09 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: @Arun: This approach is constant time once the array is build for any queries that follows. :) You know sum for all possible rectangles in the given 2d array thats makes it better than computing sum for each input. Hope it makes sense On Sun, Aug 12, 2012 at 9:07 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: Fine, the basic idea of using dp here is sum of each rectangle is a dependent sub problem. So when u find sum for smaller rectangle we can use it to compute sum of bigger rectangle with new coordinates added to previous small rectangle. So u can compute the sum array by using this formula sum[i][j] = sum[i-1][j-1] + (sum[i-1][j] - sum[i-1][j-1]) + (sum[i][j-1] - sum[i-1][j-1])+ip[i][j] [smaller rect] [that row sum value][that col sum value] On Sun, Aug 12, 2012 at 8:54 PM, Srividhya Sampath srisam261...@gmail.com wrote: @vicky can yo explain the logic behind the 'Sum Array' computation (if possible elaborately )? On Sun, Aug 12, 2012 at 8:19 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: Lets build the array for the example you gave. i/p: 0 1 2 3 4 5 6 7 8 9 10 11 (x1,y1) = (0,0) (x2,y2) = (1,2) sumArray 0 1 23 4 10 18 28 12 27 45 66 (will take O(n^2) to build above array) So now when you get coordinates as input, you can calc the sum by Ans = sumArray[x2][y2] - sumArray[x1][y1] + ip[x1][y1] For our case it will be Ans = 18-0+0 = 18 Please lemme know if any bugs with the logic. On Sun, Aug 12, 2012 at 6:27 PM, Srividhya Sampath srisam261...@gmail.com wrote: @ Vicky Can yo explain with an illustration ? On Sat, Aug 11, 2012 at 10:07 PM, ~*~VICKY~*~ venkat.jun...@gmail.com wrote: May be you can consider creating a 2d array to pre process and store all the rectangle sums as a dependent subproblem, the sum of larger rect will be currValuesAdded+OldRectSum. So when you get the coordinate as input u can calc the needed sum by subtracting sum of big rect and small rect which is not included in the given coordinates. This can be called constant time if u don't include the preprocessing time. On Sat, Aug 11, 2012 at 9:57 PM, adarsh kumar algog...@gmail.comwrote: Sum of the integers meaning? Do you mind giving an example test case? regards. On Sat, Aug 11, 2012 at 7:10 PM, Srividhya srisam261...@gmail.com wrote: hi all:) The coordinates of a rectangle will be specified. there is a matrix of integers. yo should find the sum of the integers that fall in the region specified by the coordinates . The solution to be in constant time . -- 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/-/qHSmXBshmS4J. 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. -- Cheers, Vicky -- 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. -- Cheers, Vicky -- 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
Re: [algogeeks] Constant time solution needed
say yo have 3*4 matrix... 0 1 2 3 4 5 6 7 8 9 10 11 if the co-ordinates are (0,0),(0,2),(1,0),(1,2) the o/p should be 0+1+2+4+5+6 On Sat, Aug 11, 2012 at 9:57 PM, adarsh kumar algog...@gmail.com wrote: Sum of the integers meaning? Do you mind giving an example test case? regards. On Sat, Aug 11, 2012 at 7:10 PM, Srividhya srisam261...@gmail.com wrote: hi all:) The coordinates of a rectangle will be specified. there is a matrix of integers. yo should find the sum of the integers that fall in the region specified by the coordinates . The solution to be in constant time . -- 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/-/qHSmXBshmS4J. 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. -- 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] Constant time solution needed
@ Vicky Can yo explain with an illustration ? On Sat, Aug 11, 2012 at 10:07 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: May be you can consider creating a 2d array to pre process and store all the rectangle sums as a dependent subproblem, the sum of larger rect will be currValuesAdded+OldRectSum. So when you get the coordinate as input u can calc the needed sum by subtracting sum of big rect and small rect which is not included in the given coordinates. This can be called constant time if u don't include the preprocessing time. On Sat, Aug 11, 2012 at 9:57 PM, adarsh kumar algog...@gmail.com wrote: Sum of the integers meaning? Do you mind giving an example test case? regards. On Sat, Aug 11, 2012 at 7:10 PM, Srividhya srisam261...@gmail.comwrote: hi all:) The coordinates of a rectangle will be specified. there is a matrix of integers. yo should find the sum of the integers that fall in the region specified by the coordinates . The solution to be in constant time . -- 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/-/qHSmXBshmS4J. 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. -- Cheers, Vicky -- 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] Constant time solution needed
Lets build the array for the example you gave. i/p: 0 1 2 3 4 5 6 7 8 9 10 11 (x1,y1) = (0,0) (x2,y2) = (1,2) sumArray 0 1 23 4 10 18 28 12 27 45 66 (will take O(n^2) to build above array) So now when you get coordinates as input, you can calc the sum by Ans = sumArray[x2][y2] - sumArray[x1][y1] + ip[x1][y1] For our case it will be Ans = 18-0+0 = 18 Please lemme know if any bugs with the logic. On Sun, Aug 12, 2012 at 6:27 PM, Srividhya Sampath srisam261...@gmail.comwrote: @ Vicky Can yo explain with an illustration ? On Sat, Aug 11, 2012 at 10:07 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: May be you can consider creating a 2d array to pre process and store all the rectangle sums as a dependent subproblem, the sum of larger rect will be currValuesAdded+OldRectSum. So when you get the coordinate as input u can calc the needed sum by subtracting sum of big rect and small rect which is not included in the given coordinates. This can be called constant time if u don't include the preprocessing time. On Sat, Aug 11, 2012 at 9:57 PM, adarsh kumar algog...@gmail.com wrote: Sum of the integers meaning? Do you mind giving an example test case? regards. On Sat, Aug 11, 2012 at 7:10 PM, Srividhya srisam261...@gmail.comwrote: hi all:) The coordinates of a rectangle will be specified. there is a matrix of integers. yo should find the sum of the integers that fall in the region specified by the coordinates . The solution to be in constant time . -- 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/-/qHSmXBshmS4J. 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. -- Cheers, Vicky -- 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. -- Cheers, Vicky -- 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] Constant time solution needed
You can traverse in spiral order and add each element with the specified co-ordinate. -- 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] Constant time solution needed
*within -- 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] Constant time solution needed
@Arun: How do you claim your solution to be constant time? :P On Sun, Aug 12, 2012 at 8:46 PM, Arun Kindra arunkin...@gmail.com wrote: *within -- 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. -- Cheers, Vicky -- 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] Constant time solution needed
@vicky can yo explain the logic behind the 'Sum Array' computation (if possible elaborately )? On Sun, Aug 12, 2012 at 8:19 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: Lets build the array for the example you gave. i/p: 0 1 2 3 4 5 6 7 8 9 10 11 (x1,y1) = (0,0) (x2,y2) = (1,2) sumArray 0 1 23 4 10 18 28 12 27 45 66 (will take O(n^2) to build above array) So now when you get coordinates as input, you can calc the sum by Ans = sumArray[x2][y2] - sumArray[x1][y1] + ip[x1][y1] For our case it will be Ans = 18-0+0 = 18 Please lemme know if any bugs with the logic. On Sun, Aug 12, 2012 at 6:27 PM, Srividhya Sampath srisam261...@gmail.com wrote: @ Vicky Can yo explain with an illustration ? On Sat, Aug 11, 2012 at 10:07 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: May be you can consider creating a 2d array to pre process and store all the rectangle sums as a dependent subproblem, the sum of larger rect will be currValuesAdded+OldRectSum. So when you get the coordinate as input u can calc the needed sum by subtracting sum of big rect and small rect which is not included in the given coordinates. This can be called constant time if u don't include the preprocessing time. On Sat, Aug 11, 2012 at 9:57 PM, adarsh kumar algog...@gmail.comwrote: Sum of the integers meaning? Do you mind giving an example test case? regards. On Sat, Aug 11, 2012 at 7:10 PM, Srividhya srisam261...@gmail.comwrote: hi all:) The coordinates of a rectangle will be specified. there is a matrix of integers. yo should find the sum of the integers that fall in the region specified by the coordinates . The solution to be in constant time . -- 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/-/qHSmXBshmS4J. 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. -- Cheers, Vicky -- 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. -- Cheers, Vicky -- 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] Constant time solution needed
Fine, the basic idea of using dp here is sum of each rectangle is a dependent sub problem. So when u find sum for smaller rectangle we can use it to compute sum of bigger rectangle with new coordinates added to previous small rectangle. So u can compute the sum array by using this formula sum[i][j] = sum[i-1][j-1] + (sum[i-1][j] - sum[i-1][j-1]) + (sum[i][j-1] - sum[i-1][j-1])+ip[i][j] [smaller rect] [that row sum value][that col sum value] On Sun, Aug 12, 2012 at 8:54 PM, Srividhya Sampath srisam261...@gmail.comwrote: @vicky can yo explain the logic behind the 'Sum Array' computation (if possible elaborately )? On Sun, Aug 12, 2012 at 8:19 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: Lets build the array for the example you gave. i/p: 0 1 2 3 4 5 6 7 8 9 10 11 (x1,y1) = (0,0) (x2,y2) = (1,2) sumArray 0 1 23 4 10 18 28 12 27 45 66 (will take O(n^2) to build above array) So now when you get coordinates as input, you can calc the sum by Ans = sumArray[x2][y2] - sumArray[x1][y1] + ip[x1][y1] For our case it will be Ans = 18-0+0 = 18 Please lemme know if any bugs with the logic. On Sun, Aug 12, 2012 at 6:27 PM, Srividhya Sampath srisam261...@gmail.com wrote: @ Vicky Can yo explain with an illustration ? On Sat, Aug 11, 2012 at 10:07 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: May be you can consider creating a 2d array to pre process and store all the rectangle sums as a dependent subproblem, the sum of larger rect will be currValuesAdded+OldRectSum. So when you get the coordinate as input u can calc the needed sum by subtracting sum of big rect and small rect which is not included in the given coordinates. This can be called constant time if u don't include the preprocessing time. On Sat, Aug 11, 2012 at 9:57 PM, adarsh kumar algog...@gmail.comwrote: Sum of the integers meaning? Do you mind giving an example test case? regards. On Sat, Aug 11, 2012 at 7:10 PM, Srividhya srisam261...@gmail.comwrote: hi all:) The coordinates of a rectangle will be specified. there is a matrix of integers. yo should find the sum of the integers that fall in the region specified by the coordinates . The solution to be in constant time . -- 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/-/qHSmXBshmS4J. 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. -- Cheers, Vicky -- 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. -- Cheers, Vicky -- 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. -- Cheers, Vicky -- 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] Constant time solution needed
@Arun: This approach is constant time once the array is build for any queries that follows. :) You know sum for all possible rectangles in the given 2d array thats makes it better than computing sum for each input. Hope it makes sense On Sun, Aug 12, 2012 at 9:07 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: Fine, the basic idea of using dp here is sum of each rectangle is a dependent sub problem. So when u find sum for smaller rectangle we can use it to compute sum of bigger rectangle with new coordinates added to previous small rectangle. So u can compute the sum array by using this formula sum[i][j] = sum[i-1][j-1] + (sum[i-1][j] - sum[i-1][j-1]) + (sum[i][j-1] - sum[i-1][j-1])+ip[i][j] [smaller rect] [that row sum value][that col sum value] On Sun, Aug 12, 2012 at 8:54 PM, Srividhya Sampath srisam261...@gmail.com wrote: @vicky can yo explain the logic behind the 'Sum Array' computation (if possible elaborately )? On Sun, Aug 12, 2012 at 8:19 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: Lets build the array for the example you gave. i/p: 0 1 2 3 4 5 6 7 8 9 10 11 (x1,y1) = (0,0) (x2,y2) = (1,2) sumArray 0 1 23 4 10 18 28 12 27 45 66 (will take O(n^2) to build above array) So now when you get coordinates as input, you can calc the sum by Ans = sumArray[x2][y2] - sumArray[x1][y1] + ip[x1][y1] For our case it will be Ans = 18-0+0 = 18 Please lemme know if any bugs with the logic. On Sun, Aug 12, 2012 at 6:27 PM, Srividhya Sampath srisam261...@gmail.com wrote: @ Vicky Can yo explain with an illustration ? On Sat, Aug 11, 2012 at 10:07 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: May be you can consider creating a 2d array to pre process and store all the rectangle sums as a dependent subproblem, the sum of larger rect will be currValuesAdded+OldRectSum. So when you get the coordinate as input u can calc the needed sum by subtracting sum of big rect and small rect which is not included in the given coordinates. This can be called constant time if u don't include the preprocessing time. On Sat, Aug 11, 2012 at 9:57 PM, adarsh kumar algog...@gmail.comwrote: Sum of the integers meaning? Do you mind giving an example test case? regards. On Sat, Aug 11, 2012 at 7:10 PM, Srividhya srisam261...@gmail.comwrote: hi all:) The coordinates of a rectangle will be specified. there is a matrix of integers. yo should find the sum of the integers that fall in the region specified by the coordinates . The solution to be in constant time . -- 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/-/qHSmXBshmS4J. 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. -- Cheers, Vicky -- 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. -- Cheers, Vicky -- 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. -- Cheers, Vicky -- Cheers, Vicky -- You received this message because you are subscribed to the Google Groups Algorithm Geeks
Re: [algogeeks] Constant time solution needed
a small question, if matrix has 'r' rows and 'c' columns, how many different rectangles can be there for this problem ? Space Complexity = O( (r*r)*(c*c) ) On Sat, Aug 11, 2012 at 7:10 PM, Srividhya srisam261...@gmail.com wrote: hi all:) The coordinates of a rectangle will be specified. there is a matrix of integers. yo should find the sum of the integers that fall in the region specified by the coordinates . The solution to be in constant time . -- 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/-/qHSmXBshmS4J. 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] Constant time solution needed
@venkat +1 On Sun, Aug 12, 2012 at 9:09 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: @Arun: This approach is constant time once the array is build for any queries that follows. :) You know sum for all possible rectangles in the given 2d array thats makes it better than computing sum for each input. Hope it makes sense On Sun, Aug 12, 2012 at 9:07 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: Fine, the basic idea of using dp here is sum of each rectangle is a dependent sub problem. So when u find sum for smaller rectangle we can use it to compute sum of bigger rectangle with new coordinates added to previous small rectangle. So u can compute the sum array by using this formula sum[i][j] = sum[i-1][j-1] + (sum[i-1][j] - sum[i-1][j-1]) + (sum[i][j-1] - sum[i-1][j-1])+ip[i][j] [smaller rect] [that row sum value][that col sum value] On Sun, Aug 12, 2012 at 8:54 PM, Srividhya Sampath srisam261...@gmail.com wrote: @vicky can yo explain the logic behind the 'Sum Array' computation (if possible elaborately )? On Sun, Aug 12, 2012 at 8:19 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: Lets build the array for the example you gave. i/p: 0 1 2 3 4 5 6 7 8 9 10 11 (x1,y1) = (0,0) (x2,y2) = (1,2) sumArray 0 1 23 4 10 18 28 12 27 45 66 (will take O(n^2) to build above array) So now when you get coordinates as input, you can calc the sum by Ans = sumArray[x2][y2] - sumArray[x1][y1] + ip[x1][y1] For our case it will be Ans = 18-0+0 = 18 Please lemme know if any bugs with the logic. On Sun, Aug 12, 2012 at 6:27 PM, Srividhya Sampath srisam261...@gmail.com wrote: @ Vicky Can yo explain with an illustration ? On Sat, Aug 11, 2012 at 10:07 PM, ~*~VICKY~*~ venkat.jun...@gmail.com wrote: May be you can consider creating a 2d array to pre process and store all the rectangle sums as a dependent subproblem, the sum of larger rect will be currValuesAdded+OldRectSum. So when you get the coordinate as input u can calc the needed sum by subtracting sum of big rect and small rect which is not included in the given coordinates. This can be called constant time if u don't include the preprocessing time. On Sat, Aug 11, 2012 at 9:57 PM, adarsh kumar algog...@gmail.comwrote: Sum of the integers meaning? Do you mind giving an example test case? regards. On Sat, Aug 11, 2012 at 7:10 PM, Srividhya srisam261...@gmail.comwrote: hi all:) The coordinates of a rectangle will be specified. there is a matrix of integers. yo should find the sum of the integers that fall in the region specified by the coordinates . The solution to be in constant time . -- 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/-/qHSmXBshmS4J. 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. -- Cheers, Vicky -- 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. -- Cheers, Vicky -- 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. -- Cheers, Vicky -- Cheers, Vicky
[algogeeks] Constant time solution needed
hi all:) The coordinates of a rectangle will be specified. there is a matrix of integers. yo should find the sum of the integers that fall in the region specified by the coordinates . The solution to be in constant time . -- 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/-/qHSmXBshmS4J. 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] Constant time solution needed
Sum of the integers meaning? Do you mind giving an example test case? regards. On Sat, Aug 11, 2012 at 7:10 PM, Srividhya srisam261...@gmail.com wrote: hi all:) The coordinates of a rectangle will be specified. there is a matrix of integers. yo should find the sum of the integers that fall in the region specified by the coordinates . The solution to be in constant time . -- 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/-/qHSmXBshmS4J. 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] Constant time solution needed
May be you can consider creating a 2d array to pre process and store all the rectangle sums as a dependent subproblem, the sum of larger rect will be currValuesAdded+OldRectSum. So when you get the coordinate as input u can calc the needed sum by subtracting sum of big rect and small rect which is not included in the given coordinates. This can be called constant time if u don't include the preprocessing time. On Sat, Aug 11, 2012 at 9:57 PM, adarsh kumar algog...@gmail.com wrote: Sum of the integers meaning? Do you mind giving an example test case? regards. On Sat, Aug 11, 2012 at 7:10 PM, Srividhya srisam261...@gmail.com wrote: hi all:) The coordinates of a rectangle will be specified. there is a matrix of integers. yo should find the sum of the integers that fall in the region specified by the coordinates . The solution to be in constant time . -- 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/-/qHSmXBshmS4J. 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. -- Cheers, Vicky -- 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.
