# Knight to Princess (and not reverse direction) solution using binary search

• Since most solutions solve it in reverse (which is actually pretty neat), what I cam up with is a front to back (and not back to front) solution that uses binary search to find the smallest HP required to rescue. Running time is O(n^2 log(D)), where D is the maximum value of an integer.

``````class Solution {
bool canSolve(vector<vector<int>> &dungeon, int guess) {
dungeon[0][0] += guess;
if (dungeon[0][0] <= 0) return false;
for (int i = 1; i < dungeon.size(); ++i) {
dungeon[i][0] += dungeon[i-1][0];
if (dungeon[i][0] <= 0) {
dungeon[i][0] = INT_MIN / 2;
}
}
for (int i = 1; i < dungeon[0].size(); ++i) {
dungeon[0][i] += dungeon[0][i-1];
if (dungeon[0][i] <= 0) {
dungeon[0][i] = INT_MIN / 2;
}
}
for (int i = 1; i < dungeon.size(); ++i) {
for (int j = 1; j < dungeon[0].size(); ++j) {
dungeon[i][j] += std::max(dungeon[i-1][j], dungeon[i][j-1]);
if (dungeon[i][j] <= 0) {
dungeon[i][j] = INT_MIN / 2;
}
}
}
return dungeon.back().back() != INT_MIN / 2;
}
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
if (dungeon.empty() || dungeon[0].empty()) return 1;
int lo = 1, hi = INT_MAX;
int guess = hi;
int mid = lo + (hi - lo) / 2;
while (lo != hi) {
auto dcopy = dungeon;
bool cs = canSolve(dcopy, mid);
if (cs) {
guess = mid;
hi = mid;
} else {
lo = mid + 1;
}
mid = lo + (hi - lo) / 2;
}
return guess;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.