Tightest Frame Around the Ink Blot

HardMatrix

Problem

A scanned page is an m × n grid where 1 is an inked pixel and 0 is blank. All inked pixels form one connected blot: you can get from any inked pixel to any other by moving up, down, left or right through inked pixels. You are also told the position (row, col) of one inked pixel.

Return the area of the smallest axis-aligned rectangle that contains every inked pixel. Aim for better than O(m · n): O(m log n + n log m) is achievable.

Example 1

Input:
image = [[0, 0, 1, 0], [0, 1, 1, 0], [0, 1, 0, 0]], row = 0, col = 2
Output:
6

The ink spans rows 0–2 and columns 1–2: 3 × 2 = 6.

Example 2

Input:
image = [[1]], row = 0, col = 0
Output:
1

Constraints

  • 1 ≤ m, n ≤ 1000
  • image[i][j] is 0 or 1
  • image[row][col] = 1
  • The inked pixels form a single 4-connected region.

Hint

Show the first hint

Project the image onto the columns: a column is 'inked' if any pixel in it is 1. Because the blot is connected, what do the inked columns look like?

Walkthrough

How to approach it

01Clarify before coding

  • Is the blot guaranteed to be connected? Yes, 4-connected; this is what makes binary search valid.
  • Is the given pixel inked? Yes.
  • Rectangle area in pixels? Yes: (number of rows spanned) × (number of columns spanned).

02Brute force

Scan every pixel and track the minimum and maximum row and column of inked pixels; or flood-fill from (row, col).

Cost: O(m · n) time. Correct, but it ignores the hint you were given and reads a million pixels on a 1000 × 1000 page.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.