Maximum Square Area by Removing Fences From a Field

Maximum Square Area by Removing Fences From a Field - Problem

There is a large (m - 1) x (n - 1) rectangular field with corners at (1, 1) and (m, n) containing some horizontal and vertical fences given in arrays hFences and vFences respectively.

Horizontal fences are from the coordinates (hFences[i], 1) to (hFences[i], n) and vertical fences are from the coordinates (1, vFences[i]) to (m, vFences[i]).

Return the maximum area of a square field that can be formed by removing some fences (possibly none) or -1 if it is impossible to make a square field.

Since the answer may be large, return it modulo 10⁹ + 7.

Note: The field is surrounded by two horizontal fences from the coordinates (1, 1) to (1, n) and (m, 1) to (m, n) and two vertical fences from the coordinates (1, 1) to (m, 1) and (1, n) to (m, n). These boundary fences cannot be removed.

Input & Output

Example 1 — Basic Square Formation

$ Input: m = 4, n = 3, hFences = [2, 3], vFences = [2]

› Output: 4

💡 Note: We have a 3×2 field with horizontal fences at rows 2,3 and vertical fence at column 2. We can form a 2×2 square by removing some fences, giving area = 2² = 4.

Example 2 — No Square Possible

$ Input: m = 6, n = 7, hFences = [2], vFences = [4]

› Output: -1

💡 Note: The field is 5×6 with one horizontal fence at row 2 and one vertical fence at column 4. No valid square can be formed, so return -1.

Example 3 — Large Square

$ Input: m = 5, n = 5, hFences = [], vFences = []

› Output: 16

💡 Note: Empty 4×4 field with no internal fences. The largest square is 4×4 with area = 16.

Constraints

3 ≤ m, n ≤ 10⁹
1 ≤ hFences.length, vFences.length ≤ 1000
1 < hFences[i] < m
1 < vFences[i] < n
hFences and vFences are in strictly increasing order

Visualization

Tap to expand

Understanding the Visualization

Input Field

Rectangular field with horizontal and vertical fences

Gap Analysis

Calculate gaps between consecutive fences

Square Formation

Find maximum matching gap for square

Key Takeaway

🎯 Key Insight: The maximum square size equals the largest gap that appears in both horizontal and vertical directions between consecutive fences

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is that a square can only exist where there are matching gaps between consecutive fences in both horizontal and vertical directions. The Gap-Based approach efficiently finds all possible gaps and matches them to determine the maximum square size. Time: O(H log H + V log V), Space: O(H + V).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Enumeration	O(m³n³)	O(1)	Try every possible square position and size, checking fence removal requirements
Gap-Based Optimization	O(H log H + V log V + H×V)	O(H + V)	Find all possible gaps between fences and match horizontal/vertical gaps for squares

Brute Force Enumeration — Algorithm Steps

Iterate through all possible top-left corners (i,j)
For each corner, try all possible side lengths
Check if square can be formed by removing internal fences
Track maximum valid square area

Visualization

Tap to expand

Step-by-Step Walkthrough

Position Loop

Try each top-left corner

Size Loop

Try each possible side length

Validation

Check if square has no internal fences

Code -

solution.c — C

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

int solution(int m, int n, int* hFences, int hSize, int* vFences, int vSize) {
    const int MOD = 1000000007;
    long long maxArea = -1;
    
    // Try all possible squares
    for (int top = 1; top < m; top++) {
        for (int left = 1; left < n; left++) {
            int maxSide = (m - top < n - left) ? m - top : n - left;
            for (int side = 1; side <= maxSide; side++) {
                int bottom = top + side;
                int right = left + side;
                
                // Check if this square is valid
                int valid = 1;
                for (int i = 0; i < hSize && valid; i++) {
                    if (top < hFences[i] && hFences[i] < bottom) {
                        valid = 0;
                    }
                }
                
                if (valid) {
                    for (int i = 0; i < vSize && valid; i++) {
                        if (left < vFences[i] && vFences[i] < right) {
                            valid = 0;
                        }
                    }
                }
                
                if (valid) {
                    long long area = (long long)side * side;
                    if (area > maxArea) {
                        maxArea = area;
                    }
                }
            }
        }
    }
    
    return maxArea == -1 ? -1 : (int)(maxArea % MOD);
}

int main() {
    int m, n;
    scanf("%d", &m);
    scanf("%d", &n);
    
    // Parse hFences array
    char line[10000];
    scanf(" %[^\n]", line);
    int hFences[1000], hSize = 0;
    
    if (strcmp(line, "[]") != 0) {
        char* token = strtok(line + 1, ",]");
        while (token != NULL) {
            hFences[hSize++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    // Parse vFences array
    scanf(" %[^\n]", line);
    int vFences[1000], vSize = 0;
    
    if (strcmp(line, "[]") != 0) {
        char* token = strtok(line + 1, ",]");
        while (token != NULL) {
            vFences[vSize++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    int result = solution(m, n, hFences, hSize, vFences, vSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m³n³)

Triple nested loops for position and size, with fence checking

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

8.9K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler