Matrix
Search a 2D Matrix
Write an efficient algorithm that searches for a value in an m x n matrix.
This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer
of the previous row
Input:
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: trueclass Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int start = 0;
int last = matrix[0].length - 1;
while (last >= 0 && start < matrix.length) {
if (matrix[start][last] < target)
start++;
else if (matrix[start][last] > target)
last--;
else
return true;
}
return false;
}
}Flood Fill
An image is represented by an m x n integer grid image
where image[i][j] represents the pixel value of the image.
You are also given three integers sr, sc, and newColor.
You should perform a flood fill on the image starting
from the pixel image[sr][sc].
To perform a flood fill, consider the starting pixel,
plus any pixels connected 4-directionally to the starting pixel
of the same color as the starting pixel,
plus any pixels connected 4-directionally to those pixels
(also with the same color), and so on.
Replace the color of all of the aforementioned pixels with newColor.
Return the modified image after performing the flood fill.class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
int color = image[sr][sc];
if (color != newColor)
dfs(image, sr, sc, color, newColor);
return image;
}
public void dfs(int[][] image, int r, int c, int color, int newColor) {
if (image[r][c] == color) {
image[r][c] = newColor;
if (r >= 1)
dfs(image, r - 1, c, color, newColor);
if (c >= 1)
dfs(image, r, c - 1, color, newColor);
if (r + 1 < image.length)
dfs(image, r + 1, c, color, newColor);
if (c + 1 < image[0].length)
dfs(image, r, c + 1, color, newColor);
}
}
}Max Area of Island
You are given an m x n binary matrix grid.
An island is a group of 1's (representing land) connected 4-directionally
(horizontal or vertical.) You may assume all four edges of the
grid are surrounded by water.
The area of an island is the number of cells with a value 1 in the island.
Return the maximum area of an island in grid. If there is no island, return 0.class Solution {
int[][] grid;
boolean[][] seen;
public int area(int r, int c) {
if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length ||
seen[r][c] || grid[r][c] == 0)
return 0;
seen[r][c] = true;
return (1 + area(r + 1, c) + area(r - 1, c)
+ area(r, c - 1) + area(r, c + 1));
}
public int maxAreaOfIsland(int[][] grid) {
this.grid = grid;
seen = new boolean[grid.length][grid[0].length];
int ans = 0;
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
ans = Math.max(ans, area(r, c));
}
}
return ans;
}
}Reshape the Matrix
In MATLAB, there is a handy function called reshape which
can reshape an m x n matrix into a new one with a
different size r x c keeping its original data.
You are given an m x n matrix mat and two integers r and c
representing the number of rows and the
number of columns of the wanted reshaped matrix.
Input: mat = [[1,2],[3,4]], r = 1, c = 4
Output: [[1,2,3,4]class Solution {
public int[][] matrixReshape(int[][] mat, int r, int c) {
int n = mat.length;
int m = mat[0].length;
if ((n * m) != (r * c))
return mat;
int[][] ans = new int[r][c];
int k = 0, l = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (l >= c) {
l = 0;
k++;
}
ans[k][l++] = mat[i][j];
}
}
return ans;
}
}Pascal's Triangle
Example 1:
Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]import java.util.ArrayList;
import java.util.List;
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<>();
if (numRows == 0)
return triangle;
List<Integer> firstRow = new ArrayList<>();
firstRow.add(1);
triangle.add(firstRow);
for (int i = 1; i < numRows; i++) {
List<Integer> prevRow = triangle.get(i - 1);
List<Integer> row = new ArrayList<>();
row.add(1);
for (int j = 1; j < i; j++) {
row.add(prevRow.get(j - 1) + prevRow.get(j));
}
row.add(1);
triangle.add(row);
}
return triangle;
}
}Boundary traversal of matrix
class Solution {
public static void printBoundary(int a[][], int m, int n) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0)
System.out.print(a[i][j] + " ");
else if (i == m - 1)
System.out.print(a[i][j] + " ");
else if (j == 0)
System.out.print(a[i][j] + " ");
else if (j == n - 1)
System.out.print(a[i][j] + " ");
else
System.out.print(" ");
}
System.out.println("");
}
}
public static void main(String[] args) {
int a[][] = {
{ 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 1, 2, 3, 4 },
{ 5, 6, 7, 8 }
};
printBoundary(a, 4, 4);
}
}Spirally traversing of matrix
class Solution {
// Function print matrix in spiral form
static void spiralPrint(int m, int n, int a[][]) {
int i, k = 0, l = 0;
// k - starting row index
// m - ending row index
// l - starting column index
// n - ending column index
// i - iterator
while (k < m && l < n) {
// Print the first row from the
// remaining rows
for (i = l; i < n; ++i) {
System.out.print(a[k][i] + " ");
}
k++;
// Print the last column from the
// remaining columns
for (i = k; i < m; ++i) {
System.out.print(a[i][n - 1] + " ");
}
n--;
// Print the last row from the
// remaining rows
if (k < m) {
for (i = n - 1; i >= l; --i) {
System.out.print(a[m - 1][i] + " ");
}
m--;
}
// Print the first column from the
// remaining columns
if (l < n) {
for (i = m - 1; i >= k; --i) {
System.out.print(a[i][l] + " ");
}
l++;
}
}
}
// driver program
public static void main(String[] args) {
int R = 3;
int C = 6;
int a[][] = {
{ 1, 2, 3, 4, 5, 6 },
{ 7, 8, 9, 10, 11, 12 },
{ 13, 14, 15, 16, 17, 18 }
};
spiralPrint(R, C, a);
}
}Adding two matrices
public class Solution {
static int[][] sumMatrix(int a[][], int b[][]) {
int n1 = a.length, n2 = b.length;
int m1 = a[0].length, m2 = b[0].length;
int arr[][] = new int[n1][m1];
if (n1 == n2 && m1 == m2) {
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[i].length; j++) {
arr[i][j] = a[i][j] + b[i][j];
}
}
} else {
return new int[][] {};
}
return arr;
}
}Sum of upper and lower triangles
import java.util.ArrayList;
/**
* Solution
*/
public class Solution {
static ArrayList<Integer> sumTriangles(int matrix[][], int n) {
ArrayList<Integer> arrlst = new ArrayList<>();
int uppertrig = 0;
int lowertrig = 0;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
if (j >= i) {
uppertrig += matrix[i][j];
}
if (j <= i) {
lowertrig += matrix[i][j];
}
}
}
arrlst.add(uppertrig);
arrlst.add(lowertrig);
return arrlst;
}
}Matrix Multiplication
public class Solution {
public static void main(String args[]) {
int a[][] = { { 1, 1, 1 }, { 2, 2, 2 }, { 3, 3, 3 } };
int b[][] = { { 1, 1, 1 }, { 2, 2, 2 }, { 3, 3, 3 } };
int c[][] = new int[3][3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
c[i][j] = 0;
for (int k = 0; k < 3; k++) {
c[i][j] += a[i][k] * b[k][j];
}
System.out.print(c[i][j] + " ");
}
System.out.println();
}
}
}Print matrix in snake pattern
public class Solution {
static void print(int[][] mat) {
// Traverse through all rows
for (int i = 0; i < mat.length; i++) {
// If current row is even, print from
// left to right
if (i % 2 == 0) {
for (int j = 0; j < mat[0].length; j++)
System.out.print(mat[i][j] + " ");
System.out.println();
// If current row is odd, print from
// right to left
} else {
for (int j = mat[0].length - 1; j >= 0; j--)
System.out.print(mat[i][j] + " ");
System.out.println();
}
}
}
public static void main(String[] args) {
int[][] mat = {
{ 10, 20, 30, 40 },
{ 15, 25, 35, 45 },
{ 27, 29, 37, 48 },
{ 32, 33, 39, 50 }
};
print(mat);
}
}Transpose without extra space
// Function to find transpose of a matrix.
static void swap(int mat[][], int i, int j) {
int temp = mat[i][j];
mat[i][j] = mat[j][i];
mat[j][i] = temp;
}
static void transpose(int matrix[][], int n) {
// code here
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
swap(matrix, i, j);
}
}
}Rotate by 90 degree
void rotateby90(vector<vector<int> >& matrix, int n)
{
// code here
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
swap(matrix[i][j],matrix[j][i]);
}
}
for(int i=0;i<n/2;i++){
for(int j=0;j<n;j++){
swap(matrix[i][j],matrix[n-1-i][j]);
}
}
} Reversing the columns of a Matrix
Input:
R = 4, C = 3
matrix[][] = {
{ 1, 0, 0},
{ 1, 0, 0},
{ 1, 0, 0},
{ 0, 0, 0}
}
Output:
1 1 1
1 1 1
1 1 1
1 0 0
Explanation:
The position of cells that have 1 in
the original matrix are (0,0), (1,0)
and (2,0). Therefore, all cells in row
0,1,2 are and column 0 are modified to 1. static void reverseCol(int matrix[][])
{
// code here
for(int i=0;i<matrix.length;i++){
for(int j=0;j<matrix[i].length/2;j++){
int temp=matrix[i][j];
matrix[i][j]=matrix[i][matrix[i].length-j-1];
matrix[i][matrix[i].length-j-1]=temp;
}
}
}Boolean Matrix
class Solution {
public static void modifyMatrix(int mat[][]) {
// variables to check if there are any 1
// in first row and column
boolean row_flag = false;
boolean col_flag = false;
// updating the first row and col if 1
// is encountered
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat[0].length; j++) {
if (i == 0 && mat[i][j] == 1)
row_flag = true;
if (j == 0 && mat[i][j] == 1)
col_flag = true;
if (mat[i][j] == 1) {
mat[0][j] = 1;
mat[i][0] = 1;
}
}
}
// Modify the input matrix mat[] using the
// first row and first column of Matrix mat
for (int i = 1; i < mat.length; i++) {
for (int j = 1; j < mat[0].length; j++) {
if (mat[0][j] == 1 || mat[i][0] == 1) {
mat[i][j] = 1;
}
}
}
// modify first row if there was any 1
if (row_flag == true) {
for (int i = 0; i < mat[0].length; i++) {
mat[0][i] = 1;
}
}
// modify first col if there was any 1
if (col_flag == true) {
for (int i = 0; i < mat.length; i++) {
mat[i][0] = 1;
}
}
}
/* A utility function to print a 2D matrix */
public static void printMatrix(int mat[][]) {
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat[0].length; j++) {
System.out.print(mat[i][j]);
}
System.out.println("");
}
}
// Driver function to test the above function
public static void main(String args[]) {
int mat[][] = {
{ 1, 0, 0, 1 },
{ 0, 0, 1, 0 },
{ 0, 0, 0, 0 }
};
System.out.println("Input Matrix :");
printMatrix(mat);
modifyMatrix(mat);
System.out.println("Matrix After Modification :");
printMatrix(mat);
}
}Make matrix beautiful
Input:
N = 3
matrix[][] = {
{1, 2, 3},
{4, 2, 3},
{3, 2, 1}
}
Output: 6
Explanation:
Original matrix is as follows:
1 2 3
4 2 3
3 2 1
We need to make increment in such a way
that each row and column has one time 2,
one time 3 , one time 4. For that we
need 6 operationsimport java.util.Arrays;
class Solution {
// Function to find minimum number of operations that are required
// to make the matrix beautiful.
static int findMinOperation(int matrix[][], int n)
{
int sumRow[] = new int[n];
int sumCol[] = new int[n];
Arrays.fill(sumRow, 0);
Arrays.fill(sumCol, 0);
//calculating sumRow[] and sumCol[] array.
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
sumRow[i] += matrix[i][j];
sumCol[j] += matrix[i][j];
}
}
//finding maximum sum value in either row or in column.
int maxSum = 0;
for (int i = 0; i < n; ++i)
{
maxSum = Math.max(maxSum, sumRow[i]);
maxSum = Math.max(maxSum, sumCol[i]);
}
int count = 0;
for (int i = 0, j = 0; i < n && j < n;)
{
//finding minimum increment required in either row or column.
int diff = Math.min(maxSum - sumRow[i], maxSum - sumCol[j]);
//adding difference in corresponding cell,
//sumRow[] and sumCol[] array.
matrix[i][j] += diff;
sumRow[i] += diff;
sumCol[j] += diff;
//updating the result.
count += diff;
//if ith row is satisfied, incrementing i for next iteration.
if (sumRow[i] == maxSum)
++i;
//if jth column is satisfied, incrementing j for next iteration.
if (sumCol[j] == maxSum)
++j;
}
//returning the result.
return count;
}Unique rows in boolean matrix
Input:
row = 3, col = 4
M[][] = {
{1 1 0 1},
{1 0 0 1},
{1 1 0 1}
}
Output: '1 1 0 1' & '1 0 0 1'
Explanation:
Above the matrix of size 3x4 looks like
1 1 0 1
1 0 0 1
1 1 0 1
The two unique rows are 1 1 0 1 and 1 0 0 1.import java.util.HashSet;
public class Solution {
public static void printArray(int arr[][], int row, int col) {
HashSet<String> set = new HashSet<String>();
for (int i = 0; i < row; i++) {
String s = "";
for (int j = 0; j < col; j++)
s += String.valueOf(arr[i][j]);
if (!set.contains(s)) {
set.add(s);
System.out.println(s);
}
}
}
// Driver code
public static void main(String[] args) {
int arr[][] = {
{ 0, 1, 0, 0, 1 },
{ 1, 0, 1, 1, 0 },
{ 0, 1, 0, 0, 1 },
{ 1, 1, 1, 0, 0 }
};
printArray(arr, 4, 5);
}
}Last updated