We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Most Stones Removed with Same Row or Column

Difficulty: Medium

Problem Description

On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one stone. A stone can be removed if it shares either the same row or the same column as another stone that has not been removed. Given an array stones of length n where stones[i] = [x_i, y_i] represents the location of the i-th stone, return the largest possible number of stones that can be removed.

Key Insights

  • Stones can only be removed if they are connected through rows or columns.
  • The problem can be visualized as a graph where stones are nodes and edges exist between stones sharing the same row or column.
  • The number of removable stones is maximized by determining the number of connected components in the graph.
  • Each connected component allows the removal of (size of component - 1) stones.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The problem can be approached using a graph traversal technique. We can represent the stones as nodes in a graph and connect them based on shared rows and columns. A depth-first search (DFS) or breadth-first search (BFS) can be used to find all connected components in the graph. The size of each component allows us to determine how many stones can be removed, as we can remove all but one stone from each connected component.

  1. Use a hash table to track the stones based on rows and columns.
  2. Utilize DFS or BFS to explore all stones connected through the same row or column.
  3. Count the number of stones in each connected component.
  4. The result will be the total number of stones minus the number of connected components.

Code Solutions

def removeStones(stones):
    from collections import defaultdict

    def dfs(stone):
        stack = [stone]
        count = 0
        while stack:
            s = stack.pop()
            if s not in visited:
                visited.add(s)
                count += 1
                for neighbor in row_map[s[0]] + col_map[s[1]]:
                    if neighbor not in visited:
                        stack.append(neighbor)
        return count

    row_map = defaultdict(list)
    col_map = defaultdict(list)
    
    for x, y in stones:
        row_map[x].append((x, y))
        col_map[y].append((x, y))

    visited = set()
    removable_stones = 0

    for stone in stones:
        if stone not in visited:
            component_size = dfs(stone)
            removable_stones += component_size - 1

    return removable_stones
← Back to All Questions