Search in 2D Matrix in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of search in sorted 2D matrix

What is the output of the following C++ code that searches for the target 5 in a sorted 2D matrix?

DSA C++

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    int r = 0, c = cols - 1;
    while (r < rows && c >= 0) {
        if (matrix[r][c] == target) return true;
        else if (matrix[r][c] > target) c--;
        else r++;
    }
    return false;
}

int main() {
    vector<vector<int>> matrix = {
        {1, 4, 7, 11},
        {2, 5, 8, 12},
        {3, 6, 9, 16},
        {10, 13, 14, 17}
    };
    bool found = searchMatrix(matrix, 5);
    cout << (found ? "Found" : "Not Found") << endl;
    return 0;
}

A Runtime Error

B Found

C Compilation Error

D Not Found

💡 Hint

Start searching from the top-right corner and move left or down based on comparison.

The search starts at top-right (11). Since 11 > 5, move left to 7. 7 > 5, move left to 4. 4 < 5, move down to 5. Found target 5.

❓ Predict Output

intermediate

Output when target is absent in 2D matrix

What will be the output of this C++ code searching for target 15 in the given sorted 2D matrix?

DSA C++

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    int r = 0, c = cols - 1;
    while (r < rows && c >= 0) {
        if (matrix[r][c] == target) return true;
        else if (matrix[r][c] > target) c--;
        else r++;
    }
    return false;
}

int main() {
    vector<vector<int>> matrix = {
        {1, 4, 7, 11},
        {2, 5, 8, 12},
        {3, 6, 9, 16},
        {10, 13, 14, 17}
    };
    bool found = searchMatrix(matrix, 15);
    cout << (found ? "Found" : "Not Found") << endl;
    return 0;
}

A Not Found

B Runtime Error

C Compilation Error

D Found

💡 Hint

Trace the search path carefully; 15 is not in the matrix.

The search moves from 11 to 7 to 8 to 9 to 14 to 17 and finally exits without finding 15, returning false and printing 'Not Found'.

🔧 Debug

advanced

Identify the error in 2D matrix search code

What error will this C++ code produce when searching for target 3 in a 2D matrix?

DSA C++

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    int r = 0, c = cols;
    while (r < rows && c >= 0) {
        if (matrix[r][c] == target) return true;
        else if (matrix[r][c] > target) c--;
        else r++;
    }
    return false;
}

int main() {
    vector<vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    bool found = searchMatrix(matrix, 3);
    cout << (found ? "Found" : "Not Found") << endl;
    return 0;
}

A Compilation Error

B Output: Not Found

C Output: Found

D Runtime Error: out_of_range

💡 Hint

Check the initial value of column index c.

The code initializes c = cols, which is out of bounds (max index is cols-1). Accessing matrix[r][c] causes out_of_range runtime error.

❓ Predict Output

advanced

Output of binary search on flattened 2D matrix

What is the output of this C++ code that uses binary search on a flattened 2D matrix to find target 8?

DSA C++

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    int left = 0, right = rows * cols - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int mid_value = matrix[mid / cols][mid % cols];
        if (mid_value == target) return true;
        else if (mid_value < target) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

int main() {
    vector<vector<int>> matrix = {
        {1, 3, 5, 7},
        {10, 11, 16, 20},
        {23, 30, 34, 50}
    };
    bool found = searchMatrix(matrix, 8);
    cout << (found ? "Found" : "Not Found") << endl;
    return 0;
}

A Found

B Compilation Error

C Not Found

D Runtime Error

💡 Hint

8 is not in the matrix; binary search will fail to find it.

Binary search checks middle elements but 8 is not present, so it returns false and prints 'Not Found'.

🧠 Conceptual

expert

Time complexity of search in sorted 2D matrix

Given a sorted 2D matrix where each row and column is sorted ascending, what is the time complexity of the search algorithm that starts from the top-right corner and moves left or down?

A O(m + n), where m is number of rows and n is number of columns

B O(m * n), where m is number of rows and n is number of columns

C O(log(m * n)), binary search on flattened matrix

D O(log m + log n), binary search on rows and columns separately

💡 Hint

Each step moves either one row down or one column left, never revisiting elements.

Starting from top-right, each step moves left or down, at most m + n steps, so time complexity is O(m + n).