“…c cccc x…” when I run this input, the test expects for 5, so it seems the plumber could visit any cell that he has visited before. But when I change the input to the following,
“…c cxcc c…” the test expects for 3, where I think it should be 4 as the plumber could move both sides.
Hi, we updated the question!
what is the time complexity?
The input for example 3 (grid[2][5]==0) and the solution (grid[2][5]==1) does not match, one results in 4 and the other results in 5.
Is the prev in the code suppose to represent the dp?
What is the point of adding -1 to each row of the grid?
for (List row : grid) {
row.add(-1);
}
What’s the difference between saving it to prev[i] and saving a value to prev[j]? What does it represent?
This was a hard one…
One thing I found unclear was why the solution used -inf. I figured out this is another “implementation trick”, in the case of all obstacles above (prev_max < 0), no matter how many coins we see in current segment, we will set current segment’s value to -inf (-inf + any positive = -inf).
I personally dislike the “implicit” reason, I know I would be confused if I wrote this and revisited later. So I start prev_max at -1, then add another explicit check for prev_max == -1 (segment inaccessible from above) before the line cur.append(prev_max + coins).
Thank you for pointing out, we’ve fixed it.
For convenience, we append an obstacle to the end of each row, so every segment will end with an obstacle.
Sharing python solution which modifies the input grid. grid[i][j] will gold maximum amount of coins that can be obtained at this location, and -1 if not possible to reach there
def plumber(grid: List[List[int]]) -> int:
for r in range(len(grid)): # Append a column of -1 at the end to handle last segment easier
grid[r].append(-1)
rows, cols = len(grid), len(grid[0])
r = 0 # Start from first row (update row to reflect the max coins that can be got at this location)
for r in range(rows):
start_col = 0
total = 0 # Calculate cumulative total and update it for all previous elements on hitting wall (-1)
for c in range(cols):
if grid[r][c] == 0 or grid[r][c] == 1:
total += grid[r][c]
if r > 0:
prev_max = max(prev_max, grid[r-1][c])
if grid[r][c] == -1: # or c == cols-1
for i in range(start_col, c):
if r == 0:
grid[r][i] = total
elif prev_max == -1:
grid[r][i] = -1
else:
grid[r][i] = total + prev_max
total = 0
start_col = c + 1
prev_max = -1
return max(grid[-1])
Superb question
C++ Implementation
int findSegmentStart(const vector<vector>& grid,
vector<vector>& segmentedGrid,
int row, int index) {
while (index < grid[0].size()) {
if (grid[row][index] == -1) {
segmentedGrid[row][index] = -1;
} else {
return index;
}
++index;
}
return -1;
}
int findSegmentEnd(const vector<vector>& grid,
int row, int index, int& rs) {
while (index < grid[0].size()) {
if (grid[row][index] == -1) {
return index - 1;
}
rs += grid[row][index];
++index;
}
return grid[0].size() - 1;
}
int plumber(std::vector<std::vector> grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> segmentedGrid(m, vector<int>(n));
vector<vector<pair<int, int>>> segmentLocation(m);
int start, end = -1, rs;
for (int i = 0; i < m; ++i) {
while ((start = findSegmentStart(grid, segmentedGrid, i, end + 1)) != -1) {
rs = grid[i][start];
end = findSegmentEnd(grid, i, start + 1, rs);
segmentLocation[i].push_back({start, end});
for (int j = start; j <= end; ++j) {
segmentedGrid[i][j] = rs;
}
}
end = -1;
}
for (int i = 1; i < m; ++i) {
for (const auto& segment : segmentLocation[i]) {
int max_ = -1;
for (int j = segment.first; j <= segment.second; ++j) {
max_ = max(segmentedGrid[i - 1][j], max_);
}
if (max_ != -1) {
for (int j = segment.first; j <= segment.second; ++j) {
segmentedGrid[i][j] += max_;
}
} else {
for (int j = segment.first; j <= segment.second; ++j) {
segmentedGrid[i][j] = -1;
}
}
}
}
// result will be the max value in the last row
int max_ = -1;
for (int i = 0; i < n; ++i) {
max_ = max(max_, segmentedGrid[m - 1][i]);
}
return max_;
}
A cleaner solution maybe?
def plumber(grid: List[List[int]]) → int:
grid = [[0] * len(grid[0])] + grid
grid[0].append(-1)
for i, row in enumerate(grid[1:], start=1):
row.append(-1)
start = 0
coins = 0
for j, cell in enumerate(row):
if cell == 0:
row[j] = max(row[j-1], grid[i-1][j])
if cell == 1:
row[j] = max(row[j-1], grid[i-1][j])
coins += 1
if cell == -1:
for k in range(start, j):
if row[j-1] >= 0:
row[k] = row[j-1] + coins
start = j + 1
coins = 0
return max(grid[-1])
[HELP] I am not able to figure out optimal substructure for this problem. Is there any Top down (recursive) solution available for this problem?
This problem should not be here. It doesn’t teach anything significantly valuable as far as the application of some technique goes.
Bad choice of problem for this section.