pranaypratap
BAN USERfind the median of the two sorted arrays. Divide the two arrays based on values greater and larger than the median. Merge the two distinct sets on two threads. Merge is straightforward = result(thread1).Append(result(thread2))
- pranaypratap September 24, 2017public static int FindMaxSubSquareMatrix(int[,] arr)
{
if (null == arr)
{
throw new ArgumentNullException();
}
if (arr.GetLength(0) == 0 || arr.GetLength(1) == 0)
{
return -1;
}
int[,] map = new int[arr.GetLength(0), arr.GetLength(1)];
for (int i =0; i<map.GetLength(0); i++)
{
for (int j =0; j<map.GetLength(1); j++)
{
map[i,j] = -1;
}
}
DoFindMaxSubSquareMatrix(arr, 0, 0, map);
int max = 0;
for (int i = 0; i < map.GetLength(0); i++)
{
for (int j = 0; j < map.GetLength(1); j++)
{
if (map[i,j] > max)
{
max = map[i,j];
}
}
}
return max;
}
private static int DoFindMaxSubSquareMatrix(int[,] arr, int i, int j, int[,] map)
{
if (i >= arr.GetLength(0) || j >= arr.GetLength(1))
{
// out of bounds
return 0;
}
if (map[i,j] != -1)
{
// already visited
return map[i,j];
}
int right = DoFindMaxSubSquareMatrix(arr, i + 1, j, map);
int down = DoFindMaxSubSquareMatrix(arr, i, j + 1, map);
int diagonalDown = DoFindMaxSubSquareMatrix(arr, i + 1, j + 1, map);
int subSquareSize = right == down && right == diagonalDown ? right : Math.Min(right, Math.Min(down, diagonalDown));
int result = arr[i, j] == 1 ? 1 + subSquareSize : subSquareSize;
map[i, j] = result;
return result;
}
static void Main(string[] args)
{
int[,] matrix14931 = new int[4, 4]
{
{ 1, 1, 0, 0 },
{ 0, 1, 1, 0 },
{ 0, 1, 1, 0 },
{ 1, 0, 0, 0 }
};
Console.WriteLine(ArrayQuestions.FindMaxSubSquareMatrix(matrix14931));
matrix14931 = new int[4, 4]
{
{ 1, 1, 0, 0 },
{ 0, 1, 1, 0 },
{ 0, 0, 1, 0 },
{ 1, 0, 0, 0 }
};
Console.WriteLine(ArrayQuestions.FindMaxSubSquareMatrix(matrix14931));
matrix14931 = new int[4, 4]
{
{ 1, 1, 0, 0 },
{ 0, 1, 1, 1 },
{ 0, 1, 1, 1 },
{ 1, 0, 1, 1 }
};
Console.WriteLine(ArrayQuestions.FindMaxSubSquareMatrix(matrix14931));
matrix14931 = new int[4, 5]
{
{ 1, 1, 0, 0, 1 },
{ 0, 1, 1, 1, 1 },
{ 0, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1 }
};
Console.WriteLine(ArrayQuestions.FindMaxSubSquareMatrix(matrix14931));
}
Why not try the following (nlogn):
1. sort the list
2. find the "sum so far" at each index. i.e. a[i] = Sum(a0...ai)
3. Find the item for which a[n-1] - a[i] = a[i]
e.g.
-1 1 1 2 2 5
Sums:
-1 0 1 3 5 10
10-5 = 5. we have a winner
e.x2:
-1 -1 1 2 2 2 3 5 6 7
Sums:
-1 -2 -1 1 3 5 13 19 26
26-13 = 13, we have a winner
Use a Queue to do level order traversal. When putting nodes in Q, also put the levels.
- pranaypratap October 04, 2017Every time we pop from the Queue, push to the stack along with the level. Next, push the right child in the Queue (node.right, level+1) and THEN push the left child in the Queue.
In the end, stack has the data we need.