anujarora
BAN USERIf you only concentrate over sum, then following suduku will also get passed with your approach.
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
Thus, minimum O(n) space is required to see if all elements are present or not in a row, column or 3x3 sub matrix.
@asm,
Your pseudo code really helped me understand this. I have two doubts to what you wrote
1) Exit gracefully - Shouldnt we suspend or kill all threads as well in the end?
2) While signalling the next thread, shouldnt the current thread be init with value 0, so that next time it will wait at the starting of the loop?
1. From the input array A, create a new array B which contains sum from the beginning till the current position.
5 -5 4 2 1 -3 -4 7 will become 5 0 4 6 7 -4 0 7
2. Now, take a hash map HM as <int,pair(int,int)> and put all the values in following order.
a) If no current key is present, put the key with value (i,-1) this means, i is the current index, and 0 signifies its not close yet.
b) If key is present, update value as (i,j), i is the first instance when we write it, and j is whenever we will find it again in our array.
c) For key 0, its a special case. As an empty subarray is also have a sum 0. Thus, if any 0 occurs in B, we will say from start till the current position where 0 is lying we have got a sub array. So, for 0, wherever we get last 0 in array, we will take that position.
3. Example
a) For first element 5, we will put as 5 --> (0,-1)
b) For second element 0, will put as 0 --> (0, 1)
c) For 4, we will put as 4 --> (2,-1)
d) For 6, we will put as 6 --> (3,-1)
e) For 7, we will put as 7 --> (4,-1)
f) For -4, we will put as -4 --> (5,-1)
g) For 0, we will put as 0 --> (0,6)
h) For 4, we will put as 4 --> (4,7)
4. Traverse through this hash map and find max of (j-i). In this case its 6 coming from (0,6), thus, print array from 0 to 6.
Hope my logic is clear.
It will run in O(n) time with O(n) space. This O(n) space can be saved, if we can destroy the input array which personally I dont want.
The concept is good, and the little workaround can be done to remove same pairs like (3,3) and all. But, what if two 3s are actually present in the array, then we dont want to remove.
- anujarora July 10, 2012So, overall looks wrong.