Minimum Starting Points to Cross a Grid
Updated
Problem statement
You are given an m x n grid of integers. You start on the top-left cell (0, 0) and want to reach the bottom-right cell (m - 1, n - 1). From any cell you may move one step right or one step down.
You begin with some number of points, and it must be a positive whole number. Every cell you stand on, including the first cell and the last cell, adds its value to your points, so a negative value takes points away. After each cell, your points must still be at least 1.
Return the smallest number of starting points that lets you reach the bottom-right cell along some path.
Function
minimumStartingPoints(grid: int[][]) → intExamples
Example 1
grid = [[-3,2],[-6,4]]return = 4There are two paths. Going right and then down visits -3, 2, 4. Starting with 4 points, you hold 1, then 3, then 7, so you never drop below 1. Starting with 3 would leave you with 0 after the first cell.
Going down and then right visits -3, -6, 4 and would need 10 points. The answer is 4.
Example 2
grid = [[2,5,1]]return = 1Every cell adds points, so you never run low. You still have to start with at least 1 point, so the answer is 1.
Example 3
grid = [[-1,-3,10],[0,-1,3],[0,0,-4]]return = 4The best path goes down, right, right, down and visits -1, 0, -1, 3, -4. Starting with 4 points, you hold 3, 3, 2, 5 and finally 1.
The path right, right, down, down picks up the 10, but it first drops to 4 - 1 - 3 = 0 points, so it needs 5 to start. Every other path needs even more, so the answer is 4.
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 100-1000 <= grid[i][j] <= 1000
More Nutanix Online Assessment questions
- Good SubsequencesOA · Seen Jul 2026
- Min Cost to Connect All PointsOA · Seen Jun 2026
- Digit Changes for a Multiple of 9OA · Seen Aug 2025
- Gas Station Loop StartOA · Seen Aug 2025
- Number of Players (for MTS2)OA · Seen Oct 2024
- Work Schedules (for MTS2)OA · Seen Oct 2024
- Minimum Operations to Convert ArrayOA · Seen Apr 2024
- No Adjacent CharactersOA · Seen Apr 2024
- Build a BST From a ListOA · Seen Nov 2022
- Delete Even-Valued Nodes From a Linked ListOA · Seen Nov 2022
Similar questions at other companies
- Largest Two Non-Overlapping Buildable SquaresAmerican Express · OAAmerican Express interview questions
- Minimum Grid InconvenienceAmazon · OA
- Split Array to Minimize the Largest SumInfosys · OAInfosys interview questions
- Split Array Largest SumAuxoAI · OA
- Safest Shortest Path Through a GridSnowflake · OASnowflake interview questions
- Maximum Non-Decreasing Array LengthVisa · OAVisa interview questions
- Minimum Starting Health in a GridIntuit · OAIntuit interview questions
- Maximize Array Beauty After DeletionsPoint72 · OAPoint72 interview questions
- Drone Delivery with Battery Swap StationsCisco · OACisco interview questions
- Min Elements to Remove to Make Almost Sorted ArraySalesforce · OASalesforce interview questions