1465. Maximum Area of Cake After Cuts Solution

Q: Is Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts easy or hard?

The problem is rated Medium on LeetCode because the key greedy observation is not immediately obvious. Once you realize the answer depends on the maximum gaps between cuts, the implementation becomes straightforward.

Q: Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts Python/Java solution

Python and Java implementations follow the same pattern: sort the horizontal and vertical cut arrays, compute the largest gap in each list including the edges, multiply the two gaps, and return the result modulo 1e9+7. The logic remains identical across C++, JavaScript, and other languages.

Q: How to solve Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts in O(n)?

If the cut arrays were already sorted, the problem could be solved in O(n) time by scanning once to compute the largest distance between consecutive cuts. In practice, inputs are unsorted, so sorting dominates the complexity, resulting in O(n log n).

Q: What is the best approach for Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts?

The optimal approach sorts the horizontalCuts and verticalCuts arrays and finds the maximum gap between consecutive cuts in each direction. The largest rectangle area is the product of the maximum horizontal gap and the maximum vertical gap. This greedy observation reduces the problem to simple iteration after sorting, giving O(n log n) time complexity.

Q: Is Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts asked at Google/Amazon/Meta?

This problem pattern appears frequently in interviews at companies like Amazon and Google because it tests sorting, greedy reasoning, and boundary handling. Interviewers look for the insight that the maximum rectangle is defined by the largest consecutive gaps after cuts.

Q: What data structure is used in Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts?

The solution primarily uses arrays to store cut positions. Sorting algorithms and simple iteration are applied to compute maximum gaps between adjacent elements.

Q: What is the time complexity of Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts?

The optimal greedy solution runs in O(n log n) time because both cut arrays must be sorted. After sorting, computing the largest gaps requires a single linear scan. Space complexity is O(1) extra if sorting is done in place.

The problem

You are given a rectangular cake of size h x w and two arrays of integers horizontalCuts and verticalCuts where:

horizontalCuts[i] is the distance from the top of the rectangular cake to the i^th horizontal cut and similarly, and
verticalCuts[j] is the distance from the left of the rectangular cake to the j^th vertical cut.

Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCuts. Since the answer can be a large number, return this modulo 10⁹ + 7.

Example 1:

Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
Output: 4 
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green piece of cake has the maximum area.

Example 2:

Input: h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]
Output: 6
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green and yellow pieces of cake have the maximum area.

Example 3:

Input: h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
Output: 9

Constraints:

2 <= h, w <= 10⁹
1 <= horizontalCuts.length <= min(h - 1, 10⁵)
1 <= verticalCuts.length <= min(w - 1, 10⁵)
1 <= horizontalCuts[i] < h
1 <= verticalCuts[i] < w
All the elements in horizontalCuts are distinct.
All the elements in verticalCuts are distinct.

Approach overview

Problem Overview: A rectangular cake of size h × w is cut using horizontal and vertical cut positions. Each cut divides the cake completely across that axis. After all cuts are applied, multiple smaller rectangles are formed. The task is to compute the maximum possible area of any resulting piece. Because the result can be large, return it modulo 1e9 + 7.

Approach 1: Sort and Find Maximum Gaps (Greedy) (Time: O(n log n), Space: O(1) or O(n) depending on sorting)

The key observation: the largest piece must come from the largest distance between two consecutive horizontal cuts and the largest distance between two consecutive vertical cuts. First sort both cut arrays using a standard sorting routine. Then iterate through each list to compute the maximum gap between adjacent cuts. Remember to also check the edges: 0 → first_cut and last_cut → h (or w). The maximum horizontal gap multiplied by the maximum vertical gap gives the largest rectangle area. This approach works because cuts partition the cake into independent intervals; maximizing each dimension independently yields the optimal rectangle. The final multiplication is taken modulo 1e9+7. This method relies on simple iteration over an array and a greedy selection of the largest gaps.

Approach 2: Dynamic Programming with Memoization (Time: O(n × m), Space: O(n × m))

A more exploratory method models the cake as segments between cuts and recursively computes the maximum area achievable from combinations of horizontal and vertical partitions. Memoization stores results for subproblems defined by index ranges between cuts. For each state, the algorithm considers potential partitions and calculates the maximum area from resulting segments. Although this demonstrates how subproblems overlap and how memoization avoids recomputation, it is less efficient than the greedy observation because the rectangle area is determined solely by the largest gaps. The DP approach is mostly educational for practicing recursion and caching patterns often seen in greedy-vs-DP comparisons.

Recommended for interviews: Interviewers expect the sorting + maximum gap insight. A brute or DP-style exploration shows you understand the partitioning idea, but recognizing that the largest piece is defined by the largest consecutive gaps demonstrates algorithmic clarity. The optimal solution runs in O(n log n) due to sorting and O(1) additional space, which is efficient even for large cut arrays.

Approach 1: Sort and Find Maximum Gaps

This approach involves sorting the cut arrays and finding the maximum gaps between consecutive cuts, including the edges of the cake. Once the maximum horizontal and vertical gaps are identified, the maximum possible area of a piece of cake can be obtained by multiplying these two maximum gaps.

Python

def maxArea(h, w, horizontalCuts, verticalCuts):
    MOD = 10**9 + 7
    horizontalCuts.sort()
    verticalCuts.sort()
    max_h_gap = max(horizontalCuts[0], h - horizontalCuts[-1])  # Include the edge after the last cut
    max_w_gap = max(verticalCuts[0], w - verticalCuts[-1])  # Include the edge after the last cut
    for i in range(1, len(horizontalCuts)):
        max_h_gap = max(max_h_gap, horizontalCuts[i] - horizontalCuts[i - 1])
    for i in range(1, len(verticalCuts)):
        max_w_gap = max(max_w_gap, verticalCuts[i] - verticalCuts[i - 1])
    return (max_h_gap * max_w_gap) % MOD

Java

import java.util.*;

class Solution {
    public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        long mod = 1_000_000_007;
        Arrays.sort(horizontalCuts);
        Arrays.sort(verticalCuts);
        long maxH = Math.max(horizontalCuts[0], h - horizontalCuts[horizontalCuts.length - 1]);
        long maxW = Math.max(verticalCuts[0], w - verticalCuts[verticalCuts.length - 1]);
        
        for (int i = 1; i < horizontalCuts.length; i++) {
            maxH = Math.max(maxH, horizontalCuts[i] - horizontalCuts[i - 1]);
        }
        for (int i = 1; i < verticalCuts.length; i++) {
            maxW = Math.max(maxW, verticalCuts[i] - verticalCuts[i - 1]);
        }
        return (int)((maxH * maxW) % mod);
    }
}

C++

#include <algorithm>
#include <vector>
using namespace std;

int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {
    long maxH = 0, maxW = 0, mod = 1e9 + 7;
    sort(horizontalCuts.begin(), horizontalCuts.end());
    sort(verticalCuts.begin(), verticalCuts.end());
    
    maxH = max(horizontalCuts[0], h - horizontalCuts.back());
    maxW = max(verticalCuts[0], w - verticalCuts.back());
    
    for (int i = 1; i < horizontalCuts.size(); ++i) {
        maxH = max(maxH, (long)horizontalCuts[i] - horizontalCuts[i - 1]);
    }
    for (int i = 1; i < verticalCuts.size(); ++i) {
        maxW = max(maxW, (long)verticalCuts[i] - verticalCuts[i - 1]);
    }
    return (int)((maxH * maxW) % mod);
}

JavaScript

function maxArea(h, w, horizontalCuts, verticalCuts) {
    const MOD = 1e9 + 7;
    horizontalCuts.sort((a, b) => a - b);
    verticalCuts.sort((a, b) => a - b);
    let maxH = Math.max(horizontalCuts[0], h - horizontalCuts[horizontalCuts.length - 1]);
    let maxW = Math.max(verticalCuts[0], w - verticalCuts[verticalCuts.length - 1]);
    
    for (let i = 1; i < horizontalCuts.length; i++) {
        maxH = Math.max(maxH, horizontalCuts[i] - horizontalCuts[i - 1]);
    }
    for (let i = 1; i < verticalCuts.length; i++) {
        maxW = Math.max(maxW, verticalCuts[i] - verticalCuts[i - 1]);
    }
    return (maxH * maxW) % MOD;
}

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int maxArea(int h, int w, int* horizontalCuts, int horizontalCutsSize, int* verticalCuts, int verticalCutsSize){
    const int MOD = 1e9 + 7;
    qsort(horizontalCuts, horizontalCutsSize, sizeof(int), compare);
    qsort(verticalCuts, verticalCutsSize, sizeof(int), compare);

    long maxH = horizontalCuts[0];
    long maxW = verticalCuts[0];

    for (int i = 1; i < horizontalCutsSize; i++) {
        maxH = fmax(maxH, horizontalCuts[i] - horizontalCuts[i - 1]);
    }
    maxH = fmax(maxH, h - horizontalCuts[horizontalCutsSize - 1]);

    for (int i = 1; i < verticalCutsSize; i++) {
        maxW = fmax(maxW, verticalCuts[i] - verticalCuts[i - 1]);
    }
    maxW = fmax(maxW, w - verticalCuts[verticalCutsSize - 1]);

    return (int)((maxH * maxW) % MOD);
}

using System;

public class Solution {
    public int MaxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        const int MOD = 1000000007;
        Array.Sort(horizontalCuts);
        Array.Sort(verticalCuts);
        long maxH = Math.Max(horizontalCuts[0], h - horizontalCuts[^1]);
        long maxW = Math.Max(verticalCuts[0], w - verticalCuts[^1]);
        
        for (int i = 1; i < horizontalCuts.Length; i++) {
            maxH = Math.Max(maxH, horizontalCuts[i] - horizontalCuts[i - 1]);
        }
        for (int i = 1; i < verticalCuts.Length; i++) {
            maxW = Math.Max(maxW, verticalCuts[i] - verticalCuts[i - 1]);
        }
        return (int)((maxH * maxW) % MOD);
    }
}

The function begins by sorting the horizontal and vertical cuts. It then calculates the maximum gap between each pair of consecutive cuts along with the initial and final edge to get the maximum possible length or width. This ensures we consider the pieces that extend to the end of the cake as well. The maximum area is found by multiplying these maximum gaps and returning the result modulo 10^9 + 7.

Complexity

Time Complexity: O(n log n + m log m), where n and m are the sizes of the horizontalCuts and verticalCuts arrays, due to sorting.
Space Complexity: O(1) additional space is used, as computations are done in-place.

Try this approach in the editor

Approach 2: Dynamic Programming Approach (Memoization)

This approach uses dynamic programming to store previously calculated results for maximum gaps between cuts, optimizing repeated calculations by using memoization. This is particularly useful when recalculating maximum differences thousands of times for larger input sizes.

Python

def maxAreaDP(h, w, horizontalCuts, verticalCuts):
    MOD = 10**9 + 7
    horizontalCuts.sort()
    verticalCuts.sort()
    memo = {}

    def getMaxGap(cuts, edge):
        key = (tuple(cuts), edge)
        if key in memo:
            return memo[key]
        max_gap = max(cuts[0], edge - cuts[-1])
        for i in range(1, len(cuts)):
            max_gap = max(max_gap, cuts[i] - cuts[i - 1])
        memo[key] = max_gap
        return max_gap

    max_h_gap = getMaxGap(horizontalCuts, h)
    max_w_gap = getMaxGap(verticalCuts, w)

    return (max_h_gap * max_w_gap) % MOD

JavaScript

function maxAreaDP(h, w, horizontalCuts, verticalCuts) {
    const MOD = 1e9 + 7;
    horizontalCuts.sort((a, b) => a - b);
    verticalCuts.sort((a, b) => a - b);
    const memo = {};

    function getMaxGap(cuts, edge) {
        const key = cuts.join(',') + ':' + edge;
        if (memo[key]) return memo[key];
        let maxGap = Math.max(cuts[0], edge - cuts[cuts.length - 1]);
        for (let i = 1; i < cuts.length; i++) {
            maxGap = Math.max(maxGap, cuts[i] - cuts[i - 1]);
        }
        memo[key] = maxGap;
        return maxGap;
    }

    const maxHGap = getMaxGap(horizontalCuts, h);
    const maxWGap = getMaxGap(verticalCuts, w);

    return (maxHGap * maxWGap) % MOD;
}

The Python DP solution stores results of maximum gap calculations in a dictionary (memo) to avoid repeated computation. It defines a helper function getMaxGap() for finding the largest segment gap using the memoization pattern. This stores every result fetched per list, speeding up subsequent gap queries.

Complexity

Time Complexity: O(n log n + m log m) for sorting; O(n + m) in constant time queries after sorting using memo.
Space Complexity: O(n + m) for memoization storage.

Try this approach in the editor

Approach 3: Sorting

We first sort horizontalCuts and verticalCuts separately, and then traverse both arrays to calculate the maximum difference between adjacent elements. We denote these maximum differences as x and y, respectively. Finally, we return x times y.

Note that we need to consider the boundary cases, i.e., the first and last elements of horizontalCuts and verticalCuts.

The time complexity is O(mlog m + nlog n), where m and n are the lengths of horizontalCuts and verticalCuts, respectively. The space complexity is O(log m + log n).

TypeScript

function maxArea(h: number, w: number, horizontalCuts: number[], verticalCuts: number[]): number {
    const mod = 1e9 + 7;
    horizontalCuts.push(0, h);
    verticalCuts.push(0, w);
    horizontalCuts.sort((a, b) => a - b);
    verticalCuts.sort((a, b) => a - b);
    let [x, y] = [0, 0];
    for (let i = 1; i < horizontalCuts.length; i++) {
        x = Math.max(x, horizontalCuts[i] - horizontalCuts[i - 1]);
    }
    for (let i = 1; i < verticalCuts.length; i++) {
        y = Math.max(y, verticalCuts[i] - verticalCuts[i - 1]);
    }
    return Number((BigInt(x) * BigInt(y)) % BigInt(mod));
}

func maxArea(h int, w int, horizontalCuts []int, verticalCuts []int) int {
	horizontalCuts = append(horizontalCuts, []int{0, h}...)
	verticalCuts = append(verticalCuts, []int{0, w}...)
	sort.Ints(horizontalCuts)
	sort.Ints(verticalCuts)
	x, y := 0, 0
	const mod int = 1e9 + 7
	for i := 1; i < len(horizontalCuts); i++ {
		x = max(x, horizontalCuts[i]-horizontalCuts[i-1])
	}
	for i := 1; i < len(verticalCuts); i++ {
		y = max(y, verticalCuts[i]-verticalCuts[i-1])
	}
	return (x * y) % mod
}

Rust

impl Solution {
    pub fn max_area(
        h: i32,
        w: i32,
        mut horizontal_cuts: Vec<i32>,
        mut vertical_cuts: Vec<i32>,
    ) -> i32 {
        const MOD: i64 = 1_000_000_007;

        horizontal_cuts.sort();
        vertical_cuts.sort();

        let m = horizontal_cuts.len();
        let n = vertical_cuts.len();

        let mut x = i64::max(
            horizontal_cuts[0] as i64,
            (h as i64) - (horizontal_cuts[m - 1] as i64),
        );
        let mut y = i64::max(
            vertical_cuts[0] as i64,
            (w as i64) - (vertical_cuts[n - 1] as i64),
        );

        for i in 1..m {
            x = i64::max(
                x,
                (horizontal_cuts[i] as i64) - (horizontal_cuts[i - 1] as i64),
            );
        }

        for i in 1..n {
            y = i64::max(y, (vertical_cuts[i] as i64) - (vertical_cuts[i - 1] as i64));
        }

        ((x * y) % MOD) as i32
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Sort and Find Maximum Gaps	Time Complexity: O(n log n + m log m), where n and m are the sizes of the horizontalCuts and verticalCuts arrays, due to sorting. Space Complexity: O(1) additional space is used, as computations are done in-place.
Dynamic Programming Approach (Memoization)	Time Complexity: O(n log n + m log m) for sorting; O(n + m) in constant time queries after sorting using memo. Space Complexity: O(n + m) for memoization storage.
Sorting	–

Complexity analysis

Approach	Time	Space	When to Use
Sort and Find Maximum Gaps (Greedy)	O(n log n)	O(1) extra	Best general solution; compute largest horizontal and vertical gaps after sorting cuts
Dynamic Programming (Memoization)	O(n × m)	O(n × m)	Educational exploration of partition states; rarely needed for the optimal solution

Frequently asked questions

Is Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts easy or hard?

The problem is rated Medium on LeetCode because the key greedy observation is not immediately obvious. Once you realize the answer depends on the maximum gaps between cuts, the implementation becomes straightforward.

Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts Python/Java solution

Python and Java implementations follow the same pattern: sort the horizontal and vertical cut arrays, compute the largest gap in each list including the edges, multiply the two gaps, and return the result modulo 1e9+7. The logic remains identical across C++, JavaScript, and other languages.

How to solve Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts in O(n)?

If the cut arrays were already sorted, the problem could be solved in O(n) time by scanning once to compute the largest distance between consecutive cuts. In practice, inputs are unsorted, so sorting dominates the complexity, resulting in O(n log n).

What is the best approach for Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts?

The optimal approach sorts the horizontalCuts and verticalCuts arrays and finds the maximum gap between consecutive cuts in each direction. The largest rectangle area is the product of the maximum horizontal gap and the maximum vertical gap. This greedy observation reduces the problem to simple iteration after sorting, giving O(n log n) time complexity.

Is Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts asked at Google/Amazon/Meta?

This problem pattern appears frequently in interviews at companies like Amazon and Google because it tests sorting, greedy reasoning, and boundary handling. Interviewers look for the insight that the maximum rectangle is defined by the largest consecutive gaps after cuts.

What data structure is used in Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts?

The solution primarily uses arrays to store cut positions. Sorting algorithms and simple iteration are applied to compute maximum gaps between adjacent elements.

What is the time complexity of Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts?

The optimal greedy solution runs in O(n log n) time because both cut arrays must be sorted. After sorting, computing the largest gaps requires a single linear scan. Space complexity is O(1) extra if sorting is done in place.

Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts solution and explanation

The problem

Approach overview

Approach 1: Sort and Find Maximum Gaps

Approach 2: Dynamic Programming Approach (Memoization)

Approach 3: Sorting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts solution and explanation

The problem

Approach overview

Approach 1: Sort and Find Maximum Gaps

Approach 2: Dynamic Programming Approach (Memoization)

Approach 3: Sorting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems