Problem Summary
We are given an r x c matrix containing some blocked cells.
Starting from (1,1), we must reach (r,c) using only:
up
down
left
right
A blocked cell cannot be visited.
For every cell, define:
distance(cell) = minimum Manhattan distance to any blocked cell
For a path:
path safety = minimum distance(cell) across all cells on the path
Goal:
Maximize path safety
If multiple paths have same safety, minimize number of visited cells
Return:
[maxSafety, minimumCells]
If destination cannot be reached:
[-1, -1]
Observation
The safety of a path depends on the weakest cell inside that path.
So this becomes a classic:
maximize the minimum value along a route
problem.
Step 1 — Precompute Distance From Obstacles
We first calculate for every grid cell:
closestBlocked[row][col]
This is done using multi-source BFS.
All blocked cells are inserted into the queue initially.
Since movement is 4-directional and traversal during preprocessing is allowed through every cell, BFS layers directly correspond to Manhattan distance.
Complexity:
O(r * c)
Step 2 — Find Best Possible Safety
Suppose we only allow cells having:
distance >= X
If start and destination are connected under this restriction, then safety X is achievable.
Instead of binary searching X, we process states in descending safety order using buckets.
For every cell:
best[cell] = highest minimum safety achievable till this cell
Transition:
newSafety = min(currentSafety, closestBlocked[next])
This works similarly to a max-priority BFS but avoids heap overhead.
Step 3 — Minimum Length Among Optimal Paths
Once maximum safety is known:
optimalSafety
we run a standard BFS again using only cells satisfying:
closestBlocked[cell] >= optimalSafety
The first time destination is reached gives the minimum path length.
Java Solution
import java.util.*;
class Solution {
private static final int[] DX = {-1, 1, 0, 0};
private static final int[] DY = {0, 0, -1, 1};
public int[] findOptimalPair(int rows, int cols, List<List<Integer>> blockedCells) {
int totalCells = rows * cols;
int[] dangerLevel = new int[totalCells];
Arrays.fill(dangerLevel, -1);
ArrayDeque<Integer> queue = new ArrayDeque<>();
// Multi-source BFS initialization
for (List<Integer> point : blockedCells) {
int x = point.get(0) - 1;
int y = point.get(1) - 1;
int idx = encode(x, y, cols);
if (dangerLevel[idx] == 0) {
continue;
}
dangerLevel[idx] = 0;
queue.offer(idx);
}
// Distance computation
while (!queue.isEmpty()) {
int node = queue.poll();
int x = node / cols;
int y = node % cols;
for (int d = 0; d < 4; d++) {
int nx = x + DX[d];
int ny = y + DY[d];
if (!inside(nx, ny, rows, cols)) {
continue;
}
int next = encode(nx, ny, cols);
if (dangerLevel[next] != -1) {
continue;
}
dangerLevel[next] = dangerLevel[node] + 1;
queue.offer(next);
}
}
int start = 0;
int end = totalCells - 1;
// If start or destination itself is blocked
if (dangerLevel[start] == 0 || dangerLevel[end] == 0) {
return new int[]{-1, -1};
}
int maxDistance = 0;
for (int val : dangerLevel) {
maxDistance = Math.max(maxDistance, val);
}
int[] bestSafety = new int[totalCells];
Arrays.fill(bestSafety, -1);
List<Integer>[] buckets = new ArrayList[maxDistance + 1];
for (int i = 0; i <= maxDistance; i++) {
buckets[i] = new ArrayList<>();
}
bestSafety[start] = dangerLevel[start];
buckets[bestSafety[start]].add(start);
for (int safety = maxDistance; safety >= 1; safety--) {
for (int node : buckets[safety]) {
if (bestSafety[node] != safety) {
continue;
}
int x = node / cols;
int y = node % cols;
for (int d = 0; d < 4; d++) {
int nx = x + DX[d];
int ny = y + DY[d];
if (!inside(nx, ny, rows, cols)) {
continue;
}
int next = encode(nx, ny, cols);
if (dangerLevel[next] == 0) {
continue;
}
int candidate = Math.min(safety, dangerLevel[next]);
if (candidate > bestSafety[next]) {
bestSafety[next] = candidate;
buckets[candidate].add(next);
}
}
}
}
int answerSafety = bestSafety[end];
if (answerSafety <= 0) {
return new int[]{-1, -1};
}
int[] distance = new int[totalCells];
Arrays.fill(distance, -1);
queue.clear();
distance[start] = 0;
queue.offer(start);
while (!queue.isEmpty()) {
int node = queue.poll();
if (node == end) {
break;
}
int x = node / cols;
int y = node % cols;
for (int d = 0; d < 4; d++) {
int nx = x + DX[d];
int ny = y + DY[d];
if (!inside(nx, ny, rows, cols)) {
continue;
}
int next = encode(nx, ny, cols);
if (distance[next] != -1) {
continue;
}
if (dangerLevel[next] < answerSafety) {
continue;
}
distance[next] = distance[node] + 1;
queue.offer(next);
}
}
return new int[]{answerSafety, distance[end] + 1};
}
private int encode(int x, int y, int cols) {
return x * cols + y;
}
private boolean inside(int x, int y, int rows, int cols) {
return x >= 0 && x < rows && y >= 0 && y < cols;
}
}
Complexity
Part Complexity
Multi-source BFS O(r × c)
Safety propagation O(r × c)
Final shortest path BFS O(r × c)
Overall:
Time -> O(r * c)
Space -> O(r * c)
Problem 2
Core Formula
The array is divided into four consecutive sections:
A | B | C | D
Contribution:
+A -B +C -D
So every element belongs to one of four ordered sign blocks.
Important:
i1 < i2 < i3
This means:
B cannot be empty
C cannot be empty
A and D may be empty
That restriction is the hidden trap.
DP Interpretation
Maintain four DP states:
State Meaning
plus1 currently inside first positive block
minus1 currently inside negative block
plus2 currently inside second positive block
minus2 currently inside last negative block
Transitions only move forward.
Java Solution
class Solution {
public long getMaximumGrossValue(int[] nums) {
// Prevent overflow during transitions
final long NEG_INF = Long.MIN_VALUE / 4;
long plus1 = 0;
long minus1 = NEG_INF;
long plus2 = NEG_INF;
long minus2 = NEG_INF;
for (int val : nums) {
long nextPlus1 = plus1 + val;
long nextMinus1 =
Math.max(plus1, minus1) - val;
long nextPlus2 =
Math.max(minus1, plus2) + val;
long nextMinus2 =
Math.max(plus2, minus2) - val;
plus1 = nextPlus1;
minus1 = nextMinus1;
plus2 = nextPlus2;
minus2 = nextMinus2;
}
return Math.max(plus2, minus2);
}
}
Complexity
Time -> O(n)
Space -> O(1)
Common Mistake
Many solutions incorrectly allow:
i1 <= i2 <= i3
which permits empty middle sections.
That changes the answer completely.
Example:
[10, 10, 10]
Wrong interpretation:
30
Correct strict-triplet answer:
10