Land Value Division

Problem Definition

In a city area divided into n × m continuous blocks, each block has a different value representing its land value. Two development companies, Company A and Company B, want to purchase the land in this city area.

The task is to divide all the blocks in this city area between Company A and Company B.

However, due to urban planning restrictions, the area can only be divided horizontally or vertically into two sub-regions, and each sub-region must contain at least one block. To ensure fair competition, the goal is to find a division method that minimizes the difference in total land value between the two sub-regions.

Note: Blocks cannot be further subdivided.

Input Description

• The first line contains two positive integers, n and m, representing the number of rows and columns of the city area, respectively.
• The next n lines each contain m positive integers, representing the land values of the corresponding blocks.

Output Description

• Output a single integer representing the minimum possible difference in total land value between the two sub-regions.

Input Example

3 3
1 2 3
2 1 3
1 2 3

Output Example

0

Explanation

If the area is divided as follows:

1 2 | 3
2 1 | 3
1 2 | 3

The total land values of the two sub-regions will be equal, resulting in a difference of 0.

Constraints

• 1 <= n , m <= 100；
• n and m cannot both be 1 at the same time.

Solution 1 - PreSum

Upon seeing this problem, if you want to solve it using brute force, the time complexity would be n^3.

One for loop is used to enumerate the dividing line, and two nested for loops are used to accumulate the sum within the interval.

If this problem requires finding the total sum between any two rows (or columns), based on Interval Sum, you should know how to calculate it.

It's about prefix sums: first calculate q[n], the sum of the first n rows. If you need to find the total sum from row a to row b in a matrix, then it's simply q[b] - q[a - 1].

As for why it's a - 1, refer to Interval Sum analysis; when using prefix sums, pay attention to whether intervals are open or closed at their boundaries.

This problem can also be solved using prefix sums by calculating both row-wise and column-wise sums first so that it's easy to determine the sum of two divided intervals.

The code is as follows:

class Solution:
    def minLandValueDifference(self, grid: list[list[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        total_sum = sum(sum(row) for row in grid)

        # Calculate the horizontal sums
        horizontal_sums = [sum(grid[i]) for i in range(n)]

        # Calculate the vertical sums
        vertical_sums = [sum(grid[i][j] for i in range(n)) for j in range(m)]

        # Find the minimum difference by horizontal cut
        min_diff = float('inf')
        horizontal_cut_sum = 0
        for h_sum in horizontal_sums:
            horizontal_cut_sum += h_sum
            min_diff = min(min_diff, abs(total_sum - 2 * horizontal_cut_sum))

        # Find the minimum difference by vertical cut
        vertical_cut_sum = 0
        for v_sum in vertical_sums:
            vertical_cut_sum += v_sum
            min_diff = min(min_diff, abs(total_sum - 2 * vertical_cut_sum))

        return min_diff

# Example usage
if __name__ == "__main__":
    solution = Solution()
    grid = [
        [1, 2, 3],
        [2, 1, 3],
        [1, 2, 3]
    ]
    result = solution.minLandValueDifference(grid)
    print(result)

Time complexity: O(n^2)

Solution 2 - Optimized Brute Force

In fact, this problem can be optimized based on brute force solving, so there's no need for prefix sums. When traversing row-wise and reaching the end of a row, calculate it; when traversing column-wise and reaching the end of a column, calculate it.

The time complexity is also O(n^2).

class Solution:
    def minLandValueDifference(self, grid: list[list[int]]) -> int:
        n = len(grid)  # Number of rows
        m = len(grid[0])  # Number of columns
        
        # Calculate the total sum of all elements in the grid
        total_sum = sum(sum(row) for row in grid)

        # Initialize the minimum difference with infinity
        min_diff = float('inf')

        # Calculate the minimum difference using horizontal cuts
        horizontal_count = 0
        for i in range(n):
            for j in range(m):
                horizontal_count += grid[i][j]
                # When reaching the end of the row, calculate the difference
                if j == m - 1:
                    min_diff = min(min_diff, abs(total_sum - 2 * horizontal_count))

        # Calculate the minimum difference using vertical cuts
        vertical_count = 0
        for j in range(m):
            for i in range(n):
                vertical_count += grid[i][j]
                # When reaching the end of the column, calculate the difference
                if i == n - 1:
                    min_diff = min(min_diff, abs(total_sum - 2 * vertical_count))

        return min_diff

# Example usage
if __name__ == "__main__":
    solution = Solution()
    grid = [
        [1, 2, 3],
        [2, 1, 3],
        [1, 2, 3]
    ]
    result = solution.minLandValueDifference(grid)
    print(result)

Comparison