🧐Begginner and Advanced versions 🛀 Clean Code 🪟 Clear explanation ⁉️ Q&A👊 Beat 100% 🥁
\n\n\n# What\'s the short version of your solution?\n\nFor each number in the matrix, you just need to compare it with only one number: the smallest number for 
![image.png](https://assets.leetcode.com/users/images/c5c938fa-deee-486a-a04c-894bb7c447e3_1715491365.8288958.png)\n\n\n# What\'s the short version of your solution?\n\nFor each number in the matrix, you just need to compare it with only one number: the smallest number for which a move could be possible. Then you can simply find the difference and compare it to the max score.\n\n# Why is the example comparing multiple jumps?\nThe question is trying to trick you.\n\nYou don\'t need to be worried about comparing every single element with other elements. \n\n# What if I am the current element?\n\nIf you know which element is the smallest element that could jump to you (`currentMin`), all you need to do is find the difference between yourself and  `currentMin` to find the `currentScore`. \n\n# But how can I find the currentMin?\n\nI\'ll let you know, but be patient: one step at a time. \n\nFor now, let\'s assume your `leftNeighbor` has stored the `currentMin` for itself. Also assume it\'s the case for your `topNeighbor`. So the `currentMin` will be the minimum of those.\n\n# Why?\n\nBecause anyone who could jump on you (no pun intended), could jump on either your `leftNeighbor` or your `topNeighbor`. \n\n# How to store the minimum value for the beginner version?\n \nYou can have another matrix (a two-dimentional array) for storing the minimum element that you (as the current element) could see (including yourself).\n\n# How should I find the max score?\n\nYou can keep a variable called `maxScore`. Every time you find the `currentScore` for yourself (as the current elemenet) you simply update the `maxScore`.\n\n# What\'s the time complexity?\nYou visit each element only once, so it will be the size of the input array: O(m * n)\n\n# What\'s the space complexity for the beginner version?\nFor every element of the input array, you need to store the minimum element that could reach that element with a jump (including itself). So you need space equal to the size of the input which is: O(m * n)\n\n\n\n# Code\n```\n  public int maxScore(List<List<Integer>> grid) {\n    int length = grid.size();\n    int width = grid.get(0).size();\n    int[][] minArray = new int[length][width];\n    minArray[0][0] = grid.get(0).get(0);\n    int maxScore = Integer.MIN_VALUE;\n    \n    for (int i = 1; i < length; i++) {\n      Integer currentValue = grid.get(i).get(0);\n      int leftNeighbor = minArray[i - 1][0];\n      int currentScore = currentValue - leftNeighbor;\n      maxScore = Math.max(maxScore, currentScore);\n      minArray[i][0] = Math.min(currentValue, leftNeighbor);\n    }\n\n    for (int j = 1; j < width; j++) {\n      Integer currentValue = grid.get(0).get(j);\n      int topNeighbor = minArray[0][j - 1];\n      int currentScore = currentValue - topNeighbor;\n      maxScore = Math.max(maxScore, currentScore);\n      minArray[0][j] = Math.min(currentValue, topNeighbor);\n    }\n\n    for (int i = 1; i < length; i++) {\n      for (int j = 1; j < width; j++) {\n        int leftNeighbor = minArray[i][j - 1];\n        int topNeighbor = minArray[i - 1][j];\n        int currentMin = Math.min(leftNeighbor, topNeighbor);\n        int currentScore = grid.get(i).get(j) - currentMin;\n        maxScore = Math.max(maxScore, currentScore);\n        minArray[i][j] = Math.min(grid.get(i).get(j), currentMin);\n      }\n    }\n    return maxScore;\n  }\n```\n\n# Can we solve it in O(n^2) and O(1) space?\n\nAsk your interviewer first: is it ok if I manipulate the input?\n\nIn that case, after we read the information for each element and updated the `maxScore`, we don\'t need that value anymore so we can use that space to save the `currentMinIncludingMyself` for future use.\n\n# Can you also get rid of the first 2 for loops?\n\nOnly because you asked:\n```\n\n  public int maxScore(List<List<Integer>> grid) {\n    int m = grid.size();\n    int n = grid.get(0).size();\n    int maxScore = Integer.MIN_VALUE;\n\n    for (int i = 0; i < m; i++) {\n      for (int j = 0; j < n; j++) {\n        int leftNeighbor = j == 0 ? Integer.MAX_VALUE : grid.get(i).get(j - 1);\n        int topNeighbor = i == 0 ? Integer.MAX_VALUE : grid.get(i - 1).get(j);\n        int currentMin = Math.min(leftNeighbor, topNeighbor);\n        int currentScore = grid.get(i).get(j) - currentMin;\n        maxScore = Math.max(maxScore, currentScore);\n        int currentMinIncludingMyself = Math.min(grid.get(i).get(j), currentMin);\n        grid.get(i).set(j, currentMinIncludingMyself);\n      }\n    }\n    return maxScore;\n  }\n```\n\n\n# Awesome, Last question: How can I upvote this post?\nIt\'s very challenging. I couldn\'t figure it out yet.\n\n
['Java']