aboutsummaryrefslogtreecommitdiff
path: root/grid_game.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-01-20 19:14:40 -0700
committerJack Sangdahl <[email protected]>2025-01-20 19:14:40 -0700
commitf4f6e23ad8b1f3aafee8562f9a3f64a3a76a5840 (patch)
treef14143bbe088557d169d00c2f26b01d37dc6f952 /grid_game.py
parent9a4b43e0c4e6ae790fad4e1c51bbc3b31f3490cb (diff)
downloadleetcode-f4f6e23ad8b1f3aafee8562f9a3f64a3a76a5840.tar.gz
leetcode-f4f6e23ad8b1f3aafee8562f9a3f64a3a76a5840.zip
2017. grid game
Diffstat (limited to 'grid_game.py')
-rw-r--r--grid_game.py34
1 files changed, 34 insertions, 0 deletions
diff --git a/grid_game.py b/grid_game.py
new file mode 100644
index 0000000..ded842a
--- /dev/null
+++ b/grid_game.py
@@ -0,0 +1,34 @@
+# 2017. Grid Game
+
+"""
+you are given a 0-indexed 2d array 'grid' of size '2 x n' where 'grid[r][c]'
+represents the number of points at position '[r, c]' on the matrix. two
+robots are playing a game on this matrix. both robots initially starts at
+'(0, 0)' and want to reach '(1, n - 1)'. each robot may only move to the
+right or down. at the start of the game, the first robot moves from '(0, 0)'
+to '(1, n - 1)', collecting all the points. first robot wants to minimise the
+number of points collected by the second robot. in contrast, the second robot
+wants to maximise the number of points it collects. return the number of
+points collected by the second robot
+"""
+
+
+class Solution(object):
+ def gridGame(self, grid):
+ """
+ :type grid: List[List[int]]
+ :rtype: int
+ """
+ ans, up, down = float("inf"), sum(grid[0]), 0
+ for i in range(len(grid[0])):
+ up -= grid[0][i]
+ ans = min(ans, max(up, down))
+ down += grid[1][i]
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.gridGame(grid=[[2, 5, 4], [1, 5, 1]]))
+ print(obj.gridGame(grid=[[3, 3, 1], [8, 5, 2]]))
+ print(obj.gridGame(grid=[[1, 3, 1, 15], [1, 3, 3, 1]]))