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

LeetCode Problem

Solution 0

Time Complexity: O(hlog h + vlog v + vh) for sorting

Space Complexity: O(v + h).

from typing import List

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        hcuts = [0] + sorted(horizontalCuts) + [h]
        vcuts = [0] + sorted(verticalCuts) + [w]
        max_area = 0
        for i in range(len(hcuts) - 1):
            for j in range(len(vcuts) - 1):
                area = (hcuts[i + 1] - hcuts[i]) * (vcuts[j + 1] - vcuts[j])
                max_area = max(area, max_area)
        return max_area % (10**9 + 7)

Golang

package main

import (
	"fmt"
	"math"
	"sort"
)


func maxArea(h int, w int, horizontalCuts []int, verticalCuts []int) int {
    sort.Ints(horizontalCuts)
    sort.Ints(verticalCuts)
    hcuts := append([]int{0}, append(horizontalCuts, []int{h}...)...)
    vcuts := append([]int{0}, append(verticalCuts, []int{w}...)...)
    max_area := 0
    for i := 0; i < len(hcuts) - 1; i++ {
        for j := 0; j < len(vcuts) - 1; j++ {
            area := (hcuts[i + 1] - hcuts[i]) * (vcuts[j + 1] - vcuts[j])
            if area > max_area {
                max_area = area
            }
        }
	}
    return max_area % (int(math.Pow(10, 9)) + 7)
}

func main() {
	res := maxArea(5, 4, []int{1,2,4}, []int{1,3})
	fmt.Println(res)
	if res != 4 {
		panic(fmt.Sprintf("expecting 4, got %d", res))
	}
}

Solution 1

Time Complexity: O(hlog h + vlog v) for sorting

Space Complexity: O(v + h).

from typing import List

class Solution:
    """
    Runtime: 372 ms, faster than 7.13% of Python3 online submissions for Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts.
    Memory Usage: 27.2 MB, less than 22.73% of Python3 online submissions for Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts.
    """
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        hcuts, vcuts = [0] + sorted(horizontalCuts) + [h], [0] + sorted(verticalCuts) + [w]
        return max(j - i for i, j in zip(hcuts, hcuts[1:])) * max(j - i for i, j in zip(vcuts, vcuts[1:])) % (10**9 + 7)