1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

 一刷 06/2022

Version #1 Sorting

Time O(NlogN + MlogM)

Space O(M + N) used by sorting algorithm

Runtime: 19 ms, faster than 66.24% of Java online submissions for Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts.

Memory Usage: 61.2 MB, less than 33.41% of Java online submissions for Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts.

class Solution {

    private static long MOD = (long)1e9 + 7;

    public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {

        Arrays.sort(horizontalCuts);

        Arrays.sort(verticalCuts);

        long maxH = 0;

        for (int i = 0; i <= horizontalCuts.length; i++) {

            int curr = i == horizontalCuts.length ? h : horizontalCuts[i];

            int prev = i == 0 ? 0 : horizontalCuts[i - 1];

            maxH = Math.max(maxH, curr - prev);

        }

        long maxV = 0;

        for (int i = 0; i <= verticalCuts.length; i++) {

            int curr = i == verticalCuts.length ? w : verticalCuts[i];

            int prev = i == 0 ? 0 : verticalCuts[i - 1];

            maxV = Math.max(maxV, curr - prev);

        }

        return (int)((maxH * maxV) % MOD);

    }

}