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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Most Stones Removed with Same Row or Column

Number: 984

Difficulty: Medium

Paid? No

Companies: PhonePe, Google, Tekion, Amazon, TikTok, thoughtspot

Problem Description

Given n stones positioned on a 2D grid where each stone is at a unique (x, y) coordinate, a stone can be removed if there is at least one other stone that shares the same row or column. The goal is to remove as many stones as possible such that in every connected group (where stones are connected via rows or columns) at least one stone remains.

Key Insights

  • This problem can be modeled as a graph where each stone is a node. An edge exists between two stones if they share the same row or column.
  • In each connected component of the graph, you can remove all stones except one.
  • Thus, the maximum number of stones removed equals the total number of stones minus the number of connected components.
  • Depth-First Search (DFS) or Union Find can be used to count the number of connected components.

Space and Time Complexity

Time Complexity: O(n^2) in the worst case when each stone is compared with every other stone (can be optimized with Union Find). Space Complexity: O(n) for storing visited status and mapping structures.

Solution

We solve the problem using Depth-First Search (DFS). The algorithm first builds mappings from rows and columns to stone indices. Then, it iterates through each stone; if the stone hasn't been visited, it initiates a DFS which marks all stones in the same connected component (those sharing a row or column) as visited. The number of DFS calls equals the number of connected components. Finally, the maximum stones removed is given by the total number of stones minus the number of connected components.

Code Solutions

# Python solution using DFS

def removeStones(stones):
    # Build mappings from row and column to stone indices
    row_map = {}
    col_map = {}
    n = len(stones)
    for i, (x, y) in enumerate(stones):
        row_map.setdefault(x, []).append(i)
        col_map.setdefault(y, []).append(i)

    visited = [False] * n

    # DFS to traverse all stones connected to the current stone
    def dfs(index):
        if visited[index]:
            return
        visited[index] = True
        x, y = stones[index]
        # Traverse stones in the same row
        for neighbor in row_map.get(x, []):
            if not visited[neighbor]:
                dfs(neighbor)
        # Traverse stones in the same column
        for neighbor in col_map.get(y, []):
            if not visited[neighbor]:
                dfs(neighbor)

    components = 0
    # Perform DFS for each stone that hasn't been visited
    for i in range(n):
        if not visited[i]:
            dfs(i)
            components += 1

    # The result is total stones removed = n - number of connected components
    return n - components

# Example usage:
stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
print(removeStones(stones))  # Expected Output: 5
← Back to All Questions