Dungeon Game
Updated
Problem statement
A knight starts in the top-left cell of a dungeon and must reach the princess in the bottom-right cell. The dungeon is an m x n grid of integers called dungeon. From any cell, the knight can move only one cell right or one cell down.
Each cell changes the knight's health when he enters it. A negative value is a demon that takes away that much health. A positive value is a potion that adds that much health. A 0 cell is empty. The first cell and the princess's cell count too.
Examples
Example 1
dungeon = [[-3,5,-2],[-4,-6,2],[6,-9,-1]]return = 4Go right, right, down, down. The cell values on this path are -3, 5, -2, 2 and -1, so the running change in health is -3, then 2, then 0, then 2, then 1.
The lowest point is -3, right at the first cell. Starting with 4, his health is 1, 6, 4, 6 and then 5, never below 1. Every path starts in the -3 cell, so no start below 4 works. The answer is 4.
Unlock this recently reported problem
FastPrep Pro gives you full access to interview problems reported within the last week.
- Full problem statement and constraints
- 2 more worked examples, explained
- Guided hints and editorial
- Run your code on real test cases
$99 billed yearly — or $19 month-to-month. Cancel anytime.
More Amazon Onsite Interview questions
- Number of IslandsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Cheapest Flights Within K StopsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Integer BreakONSITE INTERVIEW · Seen Nov 2026
- LFU CacheONSITE INTERVIEW · Seen Nov 2026
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Count Adjacent Symbol Pairs for BPEONSITE INTERVIEW · Seen Nov 2026
- First Non-Repeating CharacterOA · ONSITE INTERVIEW · Seen Nov 2026
- Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Longest Increasing Path in a MatrixNew Relic · PHONE SCREEN · ONSITE INTERVIEW
- Longest Increasing Path in a MatrixVisa · ONSITE INTERVIEWVisa interview questions
- Maximal Rectangle in a Binary MatrixGoogle · ONSITE INTERVIEWGoogle interview questions
- Maximum All-Ones Square Side LengthOmnissa · ONSITE INTERVIEWOmnissa interview questions
- Minimum Path SumMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Minimum Path SumBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Bomb Enemy Best CoordinatesSambaNova Systems · ONSITE INTERVIEWSambaNova Systems interview questions
- Largest Square of Ones in a GridExpedia · ONSITE INTERVIEWExpedia interview questions
- Cherry PickupInfosys · OAInfosys interview questions
- Maximum Sum RectangleDeloitte · OADeloitte interview questions
Amazon interview experiences
- Amazon SWE OA with AI Coding: 1 Experience
- Amazon SWE Intern Phone Screen Interview Experience: 1 Experience
- Amazon New Grad SDE I OA and Virtual Onsite: 1 Experience
- Amazon BIE Intern SQL and Interview Questions: 17 Experiences
- Amazon Experienced SWE AI-Assisted Debugging OA: 1 Experience
- Amazon SDE II (L5) Interview Questions: 5 Experiences