Algorithms & Data Structuresmedium

Count Objects in a Pixel Grid via an API

A pin image is an H × W grid of pixels. You do not get the raw pixels; you get an opaque grid object:

grid.height() -> int
grid.width()  -> int
grid.isBackground(r, c) -> bool
grid.isSameObject(r1, c1, r2, c2) -> bool
    // defined for two 4-adjacent, in-bounds pixels; true iff both are
    // non-background AND belong to the same object

Count the distinct objects. An object is a maximal set of non-background pixels connected through 4-adjacent pairs for which isSameObject is true. Diagonal contact does not connect — and two touching non-background pixels may still be different objects (isSameObject says false).

A A . B          A B          A .
A . . B                       . A
. . C .
=> 3             => 2         => 2

H and W up to 2000 — avoid recursion; a 2000 × 2000 object blows the stack. Each API call is O(1).

Hints

Hint 1

This is Number of Islands with one twist: adjacency is not "both non-background" but "isSameObject says so." Wire your neighbor check through the API and the rest is standard flood fill.

Hint 2

Iterate every cell; when you find a non-background pixel you haven't visited, that is one new object — BFS it to mark the rest.

Hint 3

Use an explicit queue or stack, not recursion — the constraint is written to fail recursive DFS.

Hints

Asked at