Search a 2D Matrix I

This matrix has the following properties:
        1. Integers in each row are sorted from left to right.
        2. The first integer of each row is greater than or equal to the last integer of the previous row.
    Example:
    [
        [1,   3,  5,  7],
        [10, 11, 16, 20],
        [23, 30, 34, 50]
    ]
    Given target = 3, return 1 ( 1 corresponds to true )

Return 0 / 1 ( 0 if the element is not present, 1 if the element is present ) for this problem

Approach : Use binary search to first find the row number then use binary search in that row to find the exact cell.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#include<iostream> using namespace std; bool searchMatrix(int matrix[][4], int matrixRowSize, int matrixColSize, int target) { int mid; int low = 0, row; int high = matrixRowSize - 1; row = -1; while(low <= high){ mid = (low + high) / 2; if(target <= matrix[mid][matrixColSize - 1] && target >= matrix[mid][0]){ row = mid; break; }else if(target < matrix[mid][0]){ high = mid - 1; }else if(target > matrix[mid][matrixColSize - 1]){ low = mid + 1; } } low = 0; high = matrixColSize - 1; if(row != -1){ while(low <= high){ mid = (low + high) / 2; if(matrix[row][mid] == target){ return true; }else if(matrix[row][mid] < target){ low = mid + 1; }else{ high = mid - 1; } } } return false; } int main(){ int matrix[3][4] = { {1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 50} }; cout << searchMatrix(matrix, 3, 4, 3); return 0; }

Read More

Anti Diagonals

Give a N*N square matrix, return an array of its anti-diagonals.

Input:  
1 2 3
4 5 6
7 8 9
Output :
[ 
  [1],
  [2, 4],
  [3, 5, 7],
  [6, 8],
  [9]
]

Approach : The point to observe here is that the sum of i (row number) and j (column number) is constant for each anti-diagonal.
For example:
Diagonal 1 has i + j = 0
Diagonal 2 has i + j = 1 
and so on.
So define s = i + j
Loop with s from 0 to 2*(N-1) (maximum sum possible) 
Now if s = i+j then j = s-i 
So we have reduced the problem to two variables: s and i (O(n^2)).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

vector<vector<int> > Solution::diagonal(vector<vector<int> > &A) { vector<vector<int>> result; vector<int> diagonal; int n = A.size(); if(n == 0) return result; for(int d = 0; d <= 2*(n-1); d++) { for(int i = 0; i <= d; i++) { int j = d - i; //continue if i or j exceeds their bounds if(i >= n || j >= n) continue; diagonal.push_back(A[i][j]); } result.push_back(diagonal); diagonal.clear(); } return result; }

Read More

Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

class Solution { public: vector<int> spiralOrder(vector<vector<int>>& matrix) { vector<int> result; int m = matrix.size(); if(m == 0){ return result; } int n = matrix[0].size(); int dir = 0; int top = 0, bottom = m - 1, left = 0, right = n - 1; while(top <= bottom && left <= right){ if(dir == 0){ for(int i = left; i <= right; i++){ result.push_back(matrix[top][i]); } top++; dir = 1; } else if(dir == 1){ for(int i = top; i <= bottom; i++){ result.push_back(matrix[i][right]); } right--; dir = 2; } else if(dir == 2){ for(int i = right; i >= left; i--){ result.push_back(matrix[bottom][i]); } bottom--; dir = 3; }else{ for(int i = bottom; i >= top; i--){ result.push_back(matrix[i][left]); } left++; dir = 0; } } return result; } };

Read More

Spiral Order Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

Example:

Given n = 3,

You should return the following matrix:

 [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

 #include <iostream>  
 using namespace std;  
 int main()  
 {  
   int n = 4;  
   int **mat = new int*[n];  
   for(int i = 0 ; i < n; i++)  
       mat[i] = new int[n];  
   int dir = 0;  
   int k = 1;  
   int top = 0, bottom = n - 1, left = 0, right = n - 1;  
   while(top <= bottom && left <= right){  
     if(dir == 0){  
       for(int i = left; i <= right; i++){  
         mat[top][i] = k++;  
       }  
       top++;  
       dir = 1;  
     }  
     else if(dir == 1){  
       for(int i = top; i <= bottom; i++){  
         mat[i][right] = k++;  
       }  
       right--;  
       dir = 2;  
     }  
     else if(dir == 2){  
       for(int i = right; i >= left; i--){  
         mat[bottom][i] = k++;  
       }  
       bottom--;  
       dir = 3;  
     }else{  
       for(int i = bottom; i >= top; i--){  
         mat[i][left] = k++;  
       }  
       left++;  
       dir = 0;  
     }  
   }  
   for(int i = 0 ; i < n; i++){  
     for(int j = 0; j < n; j++){  
       cout << mat[i][j] << " ";  
     }  
     cout << endl;  
   }  
   return 0;  
 }  

Read More