Dominant Cells

This was the other question I got in my attempt. It is a 2D grid question, and the whole difficulty is in handling the borders and ties correctly.

What the question asks

You get a grid of integers with n rows and m columns. A cell is dominant when its value is strictly greater than every one of its neighbours. Neighbours are the cells touching it by a side or by a corner, so a cell in the middle has 8 neighbours, a cell on an edge has 5, and a corner cell has 3. Return how many dominant cells the grid has.

Limits: n and m are between 1 and 500, the grid has at least 2 cells, and every value is between 1 and 100.

Function to write

def numCells(grid):
    # grid is a list of lists of int
    # return an int
    ...

HackerRank reads the number of rows, the number of columns and then the rows, builds grid, calls your function and writes the number you return.

Solution

def numCells(grid):
    rows = len(grid)
    cols = len(grid[0])
    count = 0

    for r in range(rows):
        for c in range(cols):
            value = grid[r][c]
            dominant = True

            for dr in (-1, 0, 1):
                for dc in (-1, 0, 1):
                    if dr == 0 and dc == 0:
                        continue
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] >= value:
                        dominant = False
                        break
                if not dominant:
                    break

            if dominant:
                count += 1

    return count

How it works

• The two outer loops visit every cell.
• dr and dc each take the values -1, 0 and 1. That gives 9 combinations: the cell itself (skipped with continue) and its 8 neighbours.
• 0 <= nr < rows and 0 <= nc < cols throws away positions outside the grid. Because and stops at the first false part, grid[nr][nc] is never read for an outside position.
• As soon as one neighbour is greater than or equal to the cell, the cell cannot be dominant, so both inner loops stop early.
• Each cell checks at most 8 neighbours, so a 500 by 500 grid needs about 2 million comparisons. On my machine the full 500 by 500 case ran in under a tenth of a second.

Mistakes that fail the hidden tests

• Using > instead of >= in the neighbour check. A cell equal to a neighbour is not dominant. In the sample below, the two 8s sit next to each other and neither counts.
• Negative indexes. In Python, grid[-1] is the last row, not an error. If you skip the bounds check and rely on a try/except IndexError, cells on the top row and left column get compared with cells on the opposite side of the grid. The answer is wrong and nothing crashes.
• Checking only 4 neighbours. The question counts diagonal neighbours too.
• Comparing the cell with itself. If you forget to skip dr == 0 and dc == 0, every cell is “equal to a neighbour” and the answer is always 0.
• Assuming the grid is square. Use len(grid[0]) for the column count. Grids like 1 by 2 and 3 by 1 are allowed.

Try it on sample data

A 3 by 3 grid:

print(numCells([[1, 2, 7], [4, 5, 6], [8, 8, 9]]))

Output from my run:

2

The 7 beats 2, 5 and 6, and the 9 beats 5, 6 and 8. The 8 in the bottom-left corner touches the other 8, so it is not dominant.