This is the 7th day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

Topic describes

Given a matrix M of size m by n with zero initial elements and a series of update operations on m.

The operations are represented by a two-dimensional array, where each operation is represented by an array of two positive integers A and b. The implication is to increment the value of all elements M[I][j] that match 0 <= I < a and 0 <= j < b by one.

After performing a given set of operations, you need to return the number of elements in the matrix that contain the largest integer.

Example 1: input: m = 3, n = 3 operations = [[2,2],[3,3]] output: 4 Initial state, M = [[0, 0, 0], [0, 0, 0], [0, 0, 0]] execute after the operation (2, 2], M = [[1, 1, 0], [1, 1, 0], [0, 0, 0]] after [3, 3] after the operation, M = [[2, 2, 1], [2, 2, 1], [1, 1]] The largest integer in M is 2, and there are four elements in M with the value of 2. So return 4. Source: LeetCode Link: https://leetcode-cn.com/problems/range-addition-ii Copyright belongs to The Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

  • Today’s algorithm problem of the day is arrays, specifically range summation. Reading the question, this is a two-dimensional array, and OPS is an array of operations that increment the specific array value by one.
  • So, first of all, we can use the naive solution to define the array m, n. We then iterate through the ops operation array and use the hashMap to record the values and the number of times they occur. This approach takes up too much space and does not pass all test cases.
  • And if you think about it, what the naive solution really wants is the intersection of OPS, so we can figure out the intersection of OPS, and the idea is to minimize x and y, and then x times y is the answer. The detailed code is as follows:

Through the code

  • Simple algorithm
class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        int ans = 0;
        if (ops.length == 0) {
            ans = m * n;
        } else {
            int[][] arr = new int[m][n];
            int tempMax = 0;
            Map<Integer, Integer> map = new HashMap<>();
            for (int[] op : ops) {
                for (int i = 0; i < op[0]; i++) {
                    for (int j = 0; j < op[1]; j++) {
                        arr[i][j] += 1;
                        map.put(arr[i][j], map.getOrDefault(arr[i][j], 0) + 1);
                        tempMax = Math.max(tempMax, arr[i][j]); 
                    }
                }
            }
            ans = map.getOrDefault(tempMax, 0);
        }

        returnans; }}Copy the code
  • Optimization method
class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        int ans = 0;
        if (ops.length == 0) {
            ans = m * n;
        } else {
            int minX = Integer.MAX_VALUE;
            int minY = Integer.MAX_VALUE;
            for (int[] op : ops) {
                minX = Math.min(minX, op[0]);
                minY = Math.min(minY, op[1]);
            }
            ans = minX * minY;
        }

        returnans; }}Copy the code

conclusion

  • The time complexity of the naive solution is O(m * n), the space complexity is O(m * n).
  • The time complexity of the optimized solution is O(m * n), and the space complexity is O(1).
  • Adhere to the algorithm of the day, come on!