What are ways to optimize this react app with potentially millions of components rendered

Here is an example of what it does: https://ostralyan.github.io/flood-fill/

This app is for educational purposes, and here is the source code.

Right now, anything bigger than a 100x100 grid gives me performance issues. When I say performance issues I mean that when I click a cell there's a few seconds delay before it renders the next state. My goal is to optimize this to support 1m squares (1000x1000).

Here is the algorithm I use for this approach

  floodFillIterative(i, j) {
    const oldColor = this.props.squares[i][j].color;
    const newColor = this.getUniqueRandomColor(oldColor);
    const squares = this.props.squares.slice();

    const stack = [
      [i, j]
    ];
    while (stack.length) {
      const squareCoordinates = stack.pop();
      let newI = squareCoordinates[0];
      let newJ = squareCoordinates[1];

      if (newI < 0 || newI >= this.props.squaresPerRow) continue;
      if (newJ < 0 || newJ >= this.props.squaresPerRow) continue;
      let nextSquare = squares[newI][newJ];

      if (nextSquare.color !== oldColor) continue;
      if (nextSquare.visited) continue;

      Array.prototype.push.apply(stack, [
        [newI - 1, newJ],
        [newI + 1, newJ],
        [newI, newJ - 1],
        [newI, newJ + 1],
      ]);
      nextSquare.visited = true;
      nextSquare.color = newColor;
    }
    this.setState({ squares });
    this.clearVisisted(squares);
  }

This algorithm runs in linear time so I'm not sure if optimizing the algorithm will really improve performance that much more. Although I'm open to any suggestions of optimization.

I also have a line of code here

  shouldComponentUpdate(nextProps) {
    if (nextProps.color !== this.props.color) {
      return true;
    }

    return false;
  }

That prevents the squares to rerender if nothing about them have changed. I'm looking for any other way to optimize this app.

Thanks!