A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.
Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.
If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.
Note:
The number of stones is ≥ 2 and is < 1,100.
Each stone's position will be a non-negative integer < 2^{31}.
The first stone's position is always 0.
Example 1:
[0,1,3,5,6,8,12,17]
There are a total of 8 stones.
The first stone at the 0th unit, second stone at the 1st unit,
third stone at the 3rd unit, and so on...
The last stone at the 17th unit.
Return true. The frog can jump to the last stone by jumping
1 unit to the 2nd stone, then 2 units to the 3rd stone, then
2 units to the 4th stone, then 3 units to the 6th stone,
4 units to the 7th stone, and 5 units to the 8th stone.
Example 2:
[0,1,2,3,4,8,9,11]Return false. There is no way to jump to the last stone as
the gap between the 5th and 6th stone is too large.
Seen this question in a real interview before?
Yes
No
When did you encounter this question?
last week
last month
last 3 month
last 6 month
more than 6 months
other
Which company?
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
Difficulty:Hard
Total Accepted:16.4K
Total Submissions:51.3K
Contributor:
LeetCode
Subscribe
to see which companies asked this question.