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 start at (0, 0) and want to reach (1, n-1). Each robot may only move to the right ((r, c) to (r, c + 1)) or down ((r, c) to (r + 1, c)).
At the start of the game, the first robot moves from (0, 0) to (1, n-1), collecting all the points from the cells on its path. For all cells (r, c) traversed on the path, grid[r][c] is set to 0. Then, the second robot moves from (0, 0) to (1, n-1), collecting the points on its path. Note that their paths may intersect with one another.
The first robot wants to minimize the number of points collected by the second robot. In contrast, the second robot wants to maximize the number of points it collects. If both robots play optimally, return the number of points collected by the second robot.
Example 1:
Input: grid = [[2,5,4],[1,5,1]] Output: 4 Explanation: The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue. The cells visited by the first robot are set to 0. The second robot will collect 0 + 0 + 4 + 0 = 4 points.
Example 2:
Input: grid = [[3,3,1],[8,5,2]] Output: 4 Explanation: The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue. The cells visited by the first robot are set to 0. The second robot will collect 0 + 3 + 1 + 0 = 4 points.
Example 3:
Input: grid = [[1,3,1,15],[1,3,3,1]] Output: 7 Explanation: The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue. The cells visited by the first robot are set to 0. The second robot will collect 0 + 1 + 3 + 3 + 0 = 7 points.
Constraints:
grid.length == 2n == grid[r].length1 <= n <= 5 * 1041 <= grid[r][c] <= 105This approach involves iterating over all possible pairs or combinations to find the solution. Although simplistic, it's often not the most efficient in terms of time complexity. However, if the input size is small, it could be feasible.
This C code iterates over all pairs in the array using a nested loop. The function `findSolution` prints all pairs which is a fundamental brute force exploration.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n2)
Space Complexity: O(1)
This approach leverages sorting the array and then using the two-pointer technique to efficiently identify necessary pairs. This optimization can reduce unnecessary comparisons made in the brute force approach by taking advantage of the sorted order.
This C solution first sorts the array using `qsort`, then iterates with two pointers on the left and right ends of the array. For each pair, it processes based on specific criteria.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Approach 1: Using a Brute Force Method | Time Complexity: O(n2) |
| Approach 2: Using Sorting and Two-Pointer Technique | Time Complexity: O(n log n) due to sorting |
Unique Paths - Dynamic Programming - Leetcode 62 • NeetCode • 157,703 views views
Watch 9 more video solutions →Practice Grid Game with our built-in code editor and test cases.
Practice on FleetCode