LOVE BABBAR DSC MATRIX QUESTION 3- SOLUTION

 LOVE BABBAR DSC MATRIX - SOLUTION

Q3) FIND MEDIAN IN ROW WISE SORTED MATRIX

int median(vector<vector<int>> &matrix, int r, int c){

        int min_e = INT_MAX, max_e = INT_MIN;

        //find min, max elements in matrix

        for(int i = 0; i < r; i++){

            if(min_e > matrix[i][0])

                min_e = matrix[i][0];

                

            if(max_e < matrix[i][c-1])

                max_e = matrix[i][c-1];

        }

        //binary search

        int target = (r*c + 1)/2;

        while(min_e < max_e){

            int mid = min_e + (max_e - min_e)/2;

            int place = 0;

            for(int i = 0; i < r; i++){

                place += upper_bound(matrix[i].begin(), matrix[i].begin()+c, mid) - matrix[i].begin();

            }

            if(place < target)

                min_e = mid+1;

            else 

                max_e = mid;

        }

        return min_e;

    }

LOVE BABBAR DSA CRACKER SHEET - MATRIX SOLUTIONS - QUESTION 1

LOVE BABBAR DSA CRACKER SHEET - MATRIX SOLUTIONS

1. SPIRAL TRAVERSAL OF MATRIX

https://practice.geeksforgeeks.org/problems/spirally-traversing-a-matrix-1587115621/1

METHOD - 1 - GFG PRACTICE SOLUTION

 vector<int> spirallyTraverse(vector<vector<int> > matrix, int r, int c) 

    {

        int top = 0, down = r-1, left = 0, right = c-1, i, dir = 0;

        vector<int>res;

        

        while(top <= down && left <= right){

            if(dir == 0){

                for(i = left; i <= right; i++)

                    res.push_back(matrix[top][i]);

                top++;

            }

            else if(dir == 1){

                for(i = top; i <= down; i++)

                    res.push_back(matrix[i][right]);

                right--;

            }

            else if(dir == 2){

                for(i = right; i >= left; i--)

                    res.push_back(matrix[down][i]);

                down--;

            }

            else if(dir == 3){

                for(i = down; i >= top; i--)

                    res.push_back(matrix[i][left]);

                left++;

            }

            dir = (dir+1)%4;

        }

        return res;

    }

METHOD-2 -