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.
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.

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