` ````
```

Auto Saved.

Loading Question ...

- Total Accepted:
**44750** - Total Submissions:
**122246** - Difficulty:
**Medium** -
Contributor:
**LeetCode**

According to the Wikipedia's article: "The **Game of Life**, also known simply as **Life**, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."

Given a *board* with *m* by *n* cells, each cell has an initial state *live* (1) or *dead* (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

- Any live cell with fewer than two live neighbors dies, as if caused by under-population.
- Any live cell with two or three live neighbors lives on to the next generation.
- Any live cell with more than three live neighbors dies, as if by over-population..
- Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Write a function to compute the next state (after one update) of the board given its current state.

**Follow up**:

- Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
- In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

**Credits:**

Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Subscribe to see which companies asked this question.

Show Tags

Array
Show Similar Problems

(M) Set Matrix Zeroes
Have you met this question in a real interview?

Yes

No

When did you meet this question?

last week

last month

last 3 month

last 6 month

more than 6 months

other

Which company asked you this question?

Adobe

Aetion

Affirm

Airbnb

Alation

Alibaba

Amazon

AppDynamics

Apple

Arista

Baidu

Bank of America

BlackRock

Blend Labs

Blizzard

Bloomberg

Booking

Box

Bungie

Capital One

CareerBuilder

Cisco

Citadel

Coinbase

Concur

Conviva

Coupang

Coursera

CreditEase

CVTE

Dell

Deutsche Bank

DoorDash

Dropbox

Duolingo

EasyNet

eBay

Electronic Arts

EMC

Epic Systems

Equinix

Evernote

Expedia

Facebook

FactSet

Fitbit

Flipkart

Fortinet

FourSquare

FreeWheel

GoDaddy

Goldman Sachs

Google

GrabTaxi

Groupon

HBO

Hedvig

HomeAway

HTC

Huawei

Hulu

IBG

IBM

Indeed

InnovatureLabs

Intel

IXL

Jane Street

JPMorgan

Jump Trading

Lending Club

LinkedIn

LiveRamp

Loovee

Marvel

Matlab

McKesson

Microsoft

Morgan Stanley

NetEase

Nintendo

Nutanix

Nvidia

Oracle

Orbitz

Palantir

Paypal

Pinterest

Pocket Gems

Point72

Qualcomm

Qualtrics

Qumulo

Quora

Rackspace

Redfin

Rubrik

Salesforce

Samsung

SAP

ServiceNow

Sina

Snapchat

SoftwareOne

Sony

SoundHound

Square

Sumologic

SurveyMonkey

Symantec

Tableau

Tencent

Tesorio

TinyCo

Tradeshift

TripAdvisor

Twilio

Twitter

Two Sigma

Uber

Veritas

Visa

VMware

Walmart

Wealthfront

Whitepages

Works Applications

Yahoo

Yandex

Yelp

Zappos

Zenefits

Zillow

Zynga