Divide and conquer

concept

Recursivly break down a problem into two or more sub-problems. Obtain solution to original problem by combining these solutions.

(The above image is from ASU SER501.)

[Medium] No.240 Search a 2D Matrix II

Approach: Divide and conquer (recursive)

Time Complexity: O(NlogN)

Space Complexity: O(logN)

class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { return check(0, 0, matrix, target); } bool check(int i, int j, vector<vector<int>>& matrix, int target) { if(i >= matrix.size() || j >= matrix[0].size()) return false; //base case if(matrix[i][j] == target) return true; if(matrix[i][j] > target) return false; matrix[i][j] = INT_MAX; return check(i+1, j, matrix, target) || check(i, j+1, matrix, target); } };