Most Stones Removed with Same Row or Column
Stone garden. stones[i] = [x, y] is a stone on the grid point (x, y), and no two stones share a point. Two stones line up when they have the same x (a row) or the same y (a column). You pull stones out one at a time, in any order you like, but a stone may only leave while some stone still on the grid lines up with it. Return the most stones you can pull out in total. Limits: 1 <= stones.length <= 200000, 0 <= x, y <= 10000, every point is different. The answer is always smaller than stones.length. Think about: which stones can never be pulled apart, however you order the removals? A group can hold tens of thousands of stones, so mind your stack if you search with recursion. Example: stones = [[2,3],[2,8],[6,3],[6,8],[9,5],[4,5],[7,1]] => 4 (2,3) (2,8) (6,3) (6,8) are linked by rows 2 and 6 and columns 3 and 8, so three of those four can go. (9,5) and (4,5) share column 5, so one of them can go. The stone at (7,1) lines up with nobody and stays. The stub returns -1, which is never a possible answer.
Stones sit on a grid, and you can pull one out whenever another stone still on the grid lines up with it in a row or a column. How many can you pull out in the end? Interviewers love it because the answer hides in a quiet observation about which stones are tied together, and the classic trap is comparing every pair of stones. Expect up to 200,000 stones on a grid with coordinates from 0 to 10,000.
Examples
You write
remove_stones(stones: List[List[int]])
Example 1
- Input
- stones = [[2,3],[2,8],[6,3],[6,8],[9,5],[4,5],[7,1]]
- returns
- 4
Example 2
- Input
- stones = [[3,3]]
- returns
- 0
Save this for your laptop
The editor and Run need a bigger screen. The link opens Most Stones Removed with Same Row or Column ready to code. It is free, and the editor needs no account.
The pattern behind it
Graphs
I reach for it when
- The input is edges, prerequisites or connections.
- You need cycles, an ordering or connected groups.
Say this before you type. Say whether the edges are directed, and which of the three jobs you are doing.
All 32 Graphs problemsBFS & DFS
I reach for it when
- You walk a grid, a graph or a tree and visit each cell once.
- The word shortest appears and every step costs the same.
Say this before you type. Say why breadth or depth fits, and exactly when a cell counts as visited.
All 52 BFS & DFS problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.