Design a function from matrix region sum to jigsaw problem

June 30, 2018

Introduction

It is my most favorite algorithm back in 2015. I had this algorithm exactly same one in 2015. It is called to calculate the subarea sum of matrix.

Here are a few resources.

1. matrix region sum
2. My practice on June 25, 2015, matrix region sum
3. My blog about the algorithm, June 25, 2015. The blog is here. I made a few corrections to make the blog more readable.
4. My blog on April 26, 2016, here is the link.
5. Leetcode 304 - Range Sum query 2D - Immutable

Jigsaw problem 

I recently worked on the design of a jigsaw problem. And also I had discussion with two peers. We tried to identify the problem as a classical algorithm. What is the brute force solution? what can we do better.

I read my solution and I think that it is still a brute force solution. If the function is called a lot of times, we need to reduce the time complexity.

Here is my code written less than a month.

What is the time complexity of my solve function? I put preprocessing function inside the solve function. That is a mistake since it defines time complexity to O(row * row * column * column).

The code was written but time complexity is defined by preprocessing function, which is the bigger one.

	/// <summary>
	/// Design the api to solve the pieces, so the output should be
	/// the list of edge id.
	/// </summary>
	/// <param name="pieces"></param>
	/// <param name="topLeft"></param>
	public static IList<int> OutputPieces(HashSet<Piece> pieces, Piece topLeft)
	{
	var preprocessed = preprocessingAllPieces_AtMostFourNeighbors(pieces);
	var lookup = buildPieces(pieces);
	var sorted = new List<int>();
	// process the first row
	var current = topLeft;
	while (current != null)
	{
	var neighbors = preprocessed[current.Index];
	sorted.Add(current.Index);
	current = lookup[neighbors[1]]; // 0, 1, 2, 3, check right neighbor, left, top, right, bottom clockwise
	}
	// continue to second row ...
	return sorted;
	}

view raw MyDesign_JigSaw.cs hosted with ❤ by GitHub

The solution I think will be better if I remove the preprocessing and build a dictionary outside the function. We only need to do it once. Therefore the time complexity of solve function can be lowered to O(rows * columns) since it takes O(1) time to get every piece's four neighbors.

	/// <summary>
	/// preprocess all pieces, for each piece, there is at most 4 pieces which are next to each other.
	/// We only need to save those four pieces.
	/// 0, 1, 2, 3
	/// 0 - left
	/// 1 - right
	/// 2 - top
	/// 3 - down
	/// piece id is saved in the array
	///
	/// Time complexity:
	/// n - hashset size
	/// algorithm time complexity will be O(n^2) for preprocessing
	/// </summary>
	/// <param name="pieces"></param>
	/// <returns></returns>
	public static IDictionary<int, int[]> preprocessingAllPieces_AtMostFourNeighbors(HashSet<Piece> pieces)
	{
	var neighborsOfPiece = new Dictionary<int, int[]>();
	var toArray = pieces.ToArray();
	var length = toArray.Length;
	for (int index = 0; index < toArray.Length; index++)
	{
	var currentPiece = toArray[index];
	// for each piece, at most four neighbors have to be found.
	// Four neighbors can be stored in the integer array 0 - left 1 - top 2 - right 3 - bottome
	for (int index2 = index + 1; index2 < length; index2++)
	{
	var piece2 = toArray[index2];
	// call match function to find if pieces2 is one of neighbors current piece.
	// add to neighborsOfPiece if need
	}
	}
	return neighborsOfPiece;
	}

view raw preprocessPieceNeighbor.cs hosted with ❤ by GitHub

Actually the second for loop on line 30 should include all pieces except itself.