Scale Engineer

Maximize Area of Square Hole in Grid

Med
#2623Time: O(S^2 * (L_h^2 + L_v^2)). Here, L_h and L_v are the lengths of the bar arrays, and S is the maximum possible side length (`min(L_h, L_v) + 1`). Given the constraints, this is too slow.Space: O(1), as no additional data structures are used that scale with the input size.1 company
Algorithms
Sorting
Data structures
Array
Companies
Swiggy

Prompt

You are given the two integers, n and m and two integer arrays, hBars and vBars. The grid has n + 2 horizontal and m + 2 vertical bars, creating 1 x 1 unit cells. The bars are indexed starting from 1.

You can remove some of the bars in hBars from horizontal bars and some of the bars in vBars from vertical bars. Note that other bars are fixed and cannot be removed.

Return an integer denoting the maximum area of a square-shaped hole in the grid, after removing some bars (possibly none).

 

Example 1:

Input: n = 2, m = 1, hBars = [2,3], vBars = [2]

Output: 4

Explanation:

The left image shows the initial grid formed by the bars. The horizontal bars are [1,2,3,4], and the vertical bars are [1,2,3].

One way to get the maximum square-shaped hole is by removing horizontal bar 2 and vertical bar 2.

Example 2:

Input: n = 1, m = 1, hBars = [2], vBars = [2]

Output: 4

Explanation:

To get the maximum square-shaped hole, we remove horizontal bar 2 and vertical bar 2.

Example 3:

Input: n = 2, m = 3, hBars = [2,3], vBars = [2,4]

Output: 4

Explanation:

One way to get the maximum square-shaped hole is by removing horizontal bar 3, and vertical bar 4.

 

Constraints:

  • 1 <= n <= 109
  • 1 <= m <= 109
  • 1 <= hBars.length <= 100
  • 2 <= hBars[i] <= n + 1
  • 1 <= vBars.length <= 100
  • 2 <= vBars[i] <= m + 1
  • All values in hBars are distinct.
  • All values in vBars are distinct.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach iterates through all possible side lengths for the square hole, from largest to smallest. For each side length s, it checks if it's possible to create such a hole. This requires finding a contiguous block of s-1 removable horizontal bars and s-1 removable vertical bars. The check for these consecutive sequences is done by naively iterating through the hBars and vBars arrays in a nested loop fashion.

Algorithm

  • Iterate s from min(hBars.length, vBars.length) + 1 down to 1.
  • For each s, let k = s - 1.
  • Define a helper function hasConsecutive(bars, k):
    • For each startBar in bars:
      • Assume a sequence is found.
      • For i from 1 to k-1, check if startBar + i exists in bars by iterating through bars again.
      • If any element is not found, this is not a valid sequence from startBar.
      • If all k-1 elements are found, return true.
    • If the loop finishes, return false.
  • Call hasConsecutive for hBars and vBars with k.
  • If both calls return true, we have found the maximum side s. Return s * s.
  • If the loop finishes, it means the maximum side is 1. Return 1.

Walkthrough

The main idea is to determine the maximum possible side length, s, and then calculate the area as s*s.

We can iterate on s from a maximum possible value down to 1. The first s for which a square hole is possible will be our answer. The maximum possible side length is limited by the number of removable bars, so we can start iterating from min(hBars.length, vBars.length) + 1.

For a given side s, we need to check if there exist s-1 consecutive removable bars in both hBars and vBars. We create a helper function, hasConsecutive(bars, k), which checks if the array bars contains a sequence of k consecutive integers.

This helper function works by taking each element b from bars as a potential start of a sequence and then checking if b+1, b+2, ..., b+k-1 are also present in bars. This inner check involves another loop through the bars array, leading to a high time complexity.

The first s that satisfies the condition for both hBars and vBars gives the maximum side length. If no such s > 1 is found, the answer is a 1x1 hole (area 1), which is always possible.

class Solution {    private boolean hasConsecutive(int[] bars, int k) {        if (k == 0) return true;        if (k > bars.length) return false;         for (int startBar : bars) {            boolean foundSequence = true;            for (int i = 1; i < k; i++) {                int nextBar = startBar + i;                boolean foundNext = false;                for (int bar : bars) {                    if (bar == nextBar) {                        foundNext = true;                        break;                    }                }                if (!foundNext) {                    foundSequence = false;                    break;                }            }            if (foundSequence) {                return true;            }        }        return false;    }     public int maximizeSquareHoleArea(int n, int m, int[] hBars, int[] vBars) {        int maxPossibleSide = Math.min(hBars.length, vBars.length) + 1;        for (int s = maxPossibleSide; s >= 1; s--) {            if (hasConsecutive(hBars, s - 1) && hasConsecutive(vBars, s - 1)) {                long side = s;                return (int)(side * side);            }        }        return 0; // Should be unreachable    }}

Complexity

Time

O(S^2 * (L_h^2 + L_v^2)). Here, L_h and L_v are the lengths of the bar arrays, and S is the maximum possible side length (`min(L_h, L_v) + 1`). Given the constraints, this is too slow.

Space

O(1), as no additional data structures are used that scale with the input size.

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires no extra space besides the input arrays.

Cons

  • Very inefficient due to multiple nested loops.

  • Likely to result in a 'Time Limit Exceeded' (TLE) error for the given constraints.

Solutions

class Solution {public  int maximizeSquareHoleArea(int n, int m, int[] hBars, int[] vBars) {    int x = Math.min(f(hBars), f(vBars));    return x * x;  }private  int f(int[] nums) {    Arrays.sort(nums);    int ans = 1, cnt = 1;    for (int i = 1; i < nums.length; ++i) {      if (nums[i] == nums[i - 1] + 1) {        ans = Math.max(ans, ++cnt);      } else {        cnt = 1;      }    }    return ans + 1;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem